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 ?

 

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）

 

Each testcase outputs a line of "Case #x:" , x starts from 1.
The next q line represents the answer to each operation.

 

 

 

Author

FZUACM

 

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include<vector>

#include<set>

using namespace std;

const int N = 1e5+, M = , mod = , inf = 0x3f3f3f3f;

typedef long long ll;

//不同为1，相同为0

int in[N],dis[N],head[N],t,vis[N],fa[N][],deep[N],cas=,ff[N],cur,v[N];

vector<pair<int ,int > >G[N];

set<int >s;

struct edge{int to,next,v;}e[N*];

void add(int u,int v,int val) {e[t].to = v;e[t].next = head[u];e[t].v = val; head[u]=t++;}

void dfs(int x,int f) {

    in[x] = cur;

    ff[cur] = x;

    cur++;

    for(int i=;i<G[x].size();i++) {

        if(G[x][i].first!=f) {

            dis[G[x][i].first] = dis[x]+G[x][i].second;

            dfs(G[x][i].first,x);

        }

    }

}

void dfs1(int x) {

    vis[x] =;

    for(int i=;i<=;i++) {

        if(deep[x] < (<<i)) break;

        fa[x][i] = fa[fa[x][i-]][i-];

    }

    for(int i=head[x];i;i=e[i].next) {

        if(vis[e[i].to]) continue;

        deep[e[i].to] = deep[x]+;

        fa[e[i].to][] = x;

        dfs1(e[i].to);

    }

}

int lca(int x,int y) {

    if(deep[x] < deep[y]) swap(x,y);

    int t = deep[x] - deep[y];

    for(int i=;i<=;i++)

        if(t&(<<i)) x = fa[x][i];

    for(int i=;i>=;i--)

    if(fa[x][i]!=fa[y][i]) {

        x = fa[x][i];

        y = fa[y][i];

    }

    if(x==y) return x;

    return fa[x][];

}

int solve(int u){

if (s.empty())

  return ;

 int x, y;

   set<int>::iterator it = s.lower_bound(u), itx = it;

 itx--;

 if (it == s.end() || it == s.begin()) {

  it = s.begin();

  itx = s.end();

  itx--;

 }

 y = (*it);

 x = (*itx);

  y = ff[y];

 x =ff[x];

 u=ff[u];

 //cout<<u<<" "<<x<<" "<<y<<endl;

    return dis[u]-dis[lca(u,x)]-dis[lca(u,y)]+dis[lca(x,y)];

}

void init() {

    int n,m;

    for(int i=;i<N;i++) G[i].clear();s.clear();

    memset(head,,sizeof(head));

    memset(vis,,sizeof(vis));

    memset(dis,,sizeof(dis));

     memset(v,,sizeof(v));

    memset(deep,,sizeof(deep));

    memset(ff,,sizeof(ff));

     memset(fa,,sizeof(fa));

     memset(in,,sizeof(in));

    cur=;t=;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n-;i++) {

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        G[a].push_back(make_pair(b,c));

        G[b].push_back(make_pair(a,c));

        add(a,b,c);

        add(b,a,c);

    }

    dfs(,);dfs1();int ans=;

    printf("Case #%d:\n",cas++);

    for(int i=;i<=m;i++) {

        int a,b;

        scanf("%d%d",&a,&b);

        b=in[b];

        if(a==) {

             if(!v[b]){

                             v[b]=;

                        if(s.size()==){

                            s.insert(b);

                        }

                        else{

                            ans+=solve(b);

                            s.insert(b);

                        }

                    }

        }

        else {

              if(v[b]){

                                v[b]=;

                                s.erase(b);

                                if(s.size()!=){

                                    ans-=solve(b);

                                }

                    }

        }

        printf("%d\n",ans);

    }

}

int main() {int T;

    scanf("%d",&T);

    while(T--) {

        init();

    }

    return ;

}