#P3607. 数据网络

    ID: 2814 传统题 1000ms 512MiB 尝试: 28 已通过: 17 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划树形 DP换根 DP排序与序列处理离散化数据结构树状数组树状数组倍增求第 k 小离线与分治离线查询回滚维护状态CF28002014年国家集训队十五人互测鸣谢sumix173上传

数据网络

数据网络

题目描述

一个简单的网络数据交换系统可以被描述成一棵带权无根树。每个叶子为用户,而非叶子节点则为服务器。连接服务器(或用户)与服务器的数据线则看做一条树边,边权可以看做这条数据线的长度。 两两用户之间的一次数据交换请求都可以看做这个无根树上的一条从一个叶子到另一个叶子的路径。并且,这次数据交换请求将会激活路径上的所有服务器。对于一个服务器,如果在某一时刻有至少一条数据通过,则这个服务器是激活的,反之则是失活的。同样地,这条请求也会激活路径上的所有数据线。 现在,你作为一个交换系统的管理员,要监控整个系统的运作状态。由于系统还未开发完全,你只能知道在每个时刻,有多少条数据交换的请求,以及登记某个被激活的服务器的编号(毕竟你一秒钟也干不了太多事)。 你连续监控了一段时间。现在,你要开始整理自己的监控记录了。为了检测系统的负荷是否过重,对于每条监控记录,你要求出最坏情况下,被激活的数据线长度之和的最大值。同一条数据线被多个请求激活时只计一次。 为什么是数据线长度而不是服务器个数呢?因为出题人不喜欢单位 1。

输入格式

第一行两个整数 n,mn,m,分别描述树的大小,以及监控记录的数量。 接下来 n−1n-1 行,每行三个整数 a,b,va,b,v,描述一条连接 a,ba,b 的权值为 vv 的边。 接下来 mm 行,每行两个整数 d,sd,s, 描述一个监控记录。dd 表示登记的服务器编号,ss 表示请求数。

输出格式

对于每个监控记录,输出一行一个整数,描述答案。

样例

6 3 
1 2 2
2 3 2
3 4 2
4 6 1 
3 5 10
3 1
4 1
2 2
14
13
17

样例解释

  • 记录 (3,1)(3,1) 的一种最坏情况是走路径 1→2→3→51\to2\to3\to5。
  • 记录 (4,1)(4,1) 的一种最坏情况是走路径 6→4→3→56\to4\to3\to5。
  • 记录 (2,2)(2,2) 的一种最坏情况是走两条路径 6→4→3→56\to4\to3\to5 与 1→2→3→4→61\to2\to3\to4\to6。

数据范围

n,m≤100000n,m\le100000,所有边长之和不超过 231−12^{31}-1。所有输入的整数非负。每条记录中 1≤d≤n1\le d\le n 且 dd 不是叶子。