Time Limit:24000ms
Case Time Limit:4000ms
Memory Limit:512MB

Description

Little Y has a tree of n nodes with each edge having a positive weight.

Little J has q queries, each time he will delete k edges in the tree.

Then the tree is splitted into k+1 connected componets.

Little J wants to know the sum of the distance of farthest pair of points in each connected components.

(0 when one component only has one node.)

Each query is independent with each other. This means each query is based on the original tree.

Input

First line with an integer n, indicating the number of nodes.

Then following n-1 lines, the i-th line with three integers ui, vi, wi, indicating the i-th edge weighted wi connects ui and vi.

Then following one line with an integer q, indicating the number of queries.

For each query, the first line with an integer k, then following one line with k integers, indicating the id of the deleted edges.

1<=n,q,Σk<=105,1<=w<=109

Output

For each query, output one line with an integer indicating the sum.

Sample Input
Sample Output

要求动态维护树的直径

首先按照dfs序将整棵树映射到线段树上 针对线段树每个点维护一下子树的信息 维护这个点内直径的起点和终点 还有直径的长度  那么将两个节点合并起来的操作就是枚举一下四个端点分别计算大小 然后最后再算一遍和他们各自内部的值一共六种情况 取max那么可能会说 线段树所管辖的这段区间在树上不连续怎么办 那么很显然询问会询问的都是连续的区间 所以无所谓了

那么最后求答案 怎么求 因为题目给的是限制最多切k条边 因为切的边只会划分出子树 子树在dfs序上又是连续的区间 那么显然最后最多被分成了2*k+1的区间 那么我们针对这些区间分别求即可怎么求 大致来说就是首先判断一个区间 我是否被划分子树了 如果被划分子树了就递归去求 然后剩余的部分再一个循环 暴力将他们拼起来求答案 因为有总区间数的性质 保证了复杂度

 

分类: 线段树

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论