problem
题意给定一棵树以及q个询问。初始一个空的集合。两种询问，一种是往集合里添加一个点，一种是从集合里删除已经存在的点。对于每次询问，输出把集合里的点通过树的边连在一起所需要的最小代价（每条边都有权值）思路AC代码
代码中LCA使用倍增算法。
/************************************************************************* > File Name: main.cpp > Author: znl1087 > Mail: loveCJNforever@gmail.com > Created Time: 日 7/26 13:46:25 2015 ************************************************************************/;int n,q;const int MAXN = 100005;int head[MAXN],cnt;int dir[MAXN],p[MAXN][20],dep[MAXN],tme[MAXN],t;int dfn[MAXN];struct edge{int u,v,w,next;edge(){}edge(int u,int v,int w):u(u),v(v),w(w){}}e[MAXN<<1];struct point{int id;point(){};point(int id):id(id){}bool operator < (const point & b) const{return dfn[id] < dfn[b.id];}};set<point> se;void addedge(int u,int v,int w){e[cnt] = edge(u,v,w),e[cnt].next = head[u];head[u] = cnt++;e[cnt] = edge(v,u,w),e[cnt].next = head[v];head[v] = cnt++;}void dfs(int u){tme[t++] = u;for(int i = head[u];i!=-1;i = e[i].next){int v = e[i].v;if(!dep[v]){dir[v] = dir[u] + e[i].w;dep[v] = dep[u]+1;p[v][0] = u;dfs(v);}}}void makep(int st){dfs(st);for(int j=1;(1<<j)<=n;j++)for(int i=1;i<=n;i++)if(p[i][j-1]!=-1)p[i][j] = p[p[i][j-1]][j-1];}int LCA(int a,int b){if(dep[a] < dep[b])swap(a,b);int i;for(i = 0; (1<<i)<=dep[a];i++);i–;for(int j=i;j>=0;j–)if(dep[a]-(1<<j)>=dep[b])a = p[a][j];if(a == b)return a;for(int j = i;j >= 0;j–){if(p[a][j] != -1 && p[a][j] != p[b][j]){a = p[a][j];b = p[b][j];}}return p[a][0];}int main(){int T;cin>>T;for(int cas = 1;cas <= T;cas++){se.clear();printf(“Case #%d:\n”,cas);memset(head,-1,sizeof(head));memset(p,-1,sizeof(p));memset(dep,0,sizeof(dep));memset(dir,0,sizeof(dir));cnt = t = 0;scanf(“%d%d”,&n,&q);int u,v,w;dep[1] = 1;for(int i=1;i<n;i++){scanf(“%d%d%d”,&u,&v,&w);addedge(u, v, w);}makep(1);for(int i=0;i<t;i++)dfn[tme[i]] = i;//for(int i=0;i<t;i++)printf(“%d “,tme[i]);int st = 0;while(q–){int op,num;scanf(“%d%d”,&op,&num);if(op == 1){if(se.empty()){puts(“0”);se.insert(point(num));continue;}if(se.find(point(num))!=se.end()){printf(“%d\n”,st);continue;}set<point>::iterator it = se.lower_bound(point(num));if(it == se.begin() || it == se.end()){int x = (se.begin())->id,y = (–se.end())->id;st += (dir[num] – dir[LCA(x,num)]-dir[LCA(y,num)] + dir[LCA(x,y)]);}else{int x = (it–)->id, y = (it)->id;st += (dir[num] – dir[LCA(x,num)]-dir[LCA(y,num)] + dir[LCA(x,y)]);}se.insert(point(num);printf(“%d\n”,st);}else{if(se.find(point(num))==se.end()){printf(“%d\n”,st);continue;}se.erase(point(num));if(se.empty()){puts(“0”);se.insert(point(num));continue;}set<point>::iterator it = se.lower_bound(point(num));if(it == se.begin() || it == se.end()){int x = (se.begin())->id,y = (–se.end())->id;st -= (dir[num] – dir[LCA(x,num)]-dir[LCA(y,num)] + dir[LCA(x,y)]);}else{int x = (it–)->id, y = (it)->id;st -= (dir[num] – dir[LCA(x,num)]-dir[LCA(y,num)] + dir[LCA(x,y)]);}printf(“%d\n”,st);}}}return 0;}
，而你自己根本不想从中跑出来。学习啦分享旅行唯美心情说说语录，仅供参考！
