Annoying problem
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 203 Accepted Submission(s): 60 Problem Description
Coco has a tree, whose nodes are conveniently labeled by 1,2,…,n, which has n-1 edge，each edge has a weight. An existing set S is initially empty. Now there are two kinds of operation: 1 x： If the node x is not in the set S, add node x to the set S 2 x： If the node x is in the set S,delete node x from the set S Now there is a annoying problem: In order to select a set of edges from tree after each operation which makes any two nodes in set S connected. What is the minimum of the sum of the selected edges’ weight ?
Input
one integer number T is described in the first line represents the group number of testcases.( T<=10 ) For each test: The first line has 2 integer number n,q(0<n,q<=100000) describe the number of nodes and the number of operations. The following n-1 lines each line has 3 integer number u,v,w describe that between node u and node v has an edge weight w.(1<=u,v<=n,1<=w<=100) The following q lines each line has 2 integer number x,y describe one operation.（x=1 or 2,1<=y<=n）
Output
Each testcase outputs a line of "Case #x:" , x starts from 1. The next q line represents the answer to each operation.
Sample Input
1 6 5 1 2 2 1 5 2 5 6 2 2 4 2 2 3 2 1 5 1 3 1 4 1 2 2 5
Sample Output
Case #1: 0 6 8 8 4
Author
FZUACM
Source
#includeusing namespace std;#define prt(k) cerr<<#k" = "< < > i & 1) x = f[x][i]; return x;}int LCA(int x, int y){ if (dep[x] > dep[y]) swap(x, y); ///dep[x] <= dep[y]; y = swim(y, dep[y] - dep[x]); if (x == y) return y; for (int i=maxh; i>=0; i--) { if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; } return f[x][0];}int Q;set se;set ::iterator it;int dist(int x, int y){ int lca = LCA(x, y); return len[x] - len[lca] + len[y] - len[lca];}int solve(int u){ if (se.empty()) return 0; int x, y; int t = *se.begin(); it = se.lower_bound( u); y = *it; it--; x = *(it ); int t2 = *se.rbegin(); x = id[x]; y = id[y]; if (t2 < u || t > u) { x = id[t]; y = id[t2]; } u = id[u]; return len[u] - len[LCA(x,u) ] - len[LCA(y,u)] + len[LCA(x,y) ];}int main(){ int re; cin>>re; int ca=1; while (re--) { cin>>n>>Q; mm = 0; memset(head,-1,sizeof head); for (int i=0; i