题意
- 给定一棵树以及q个询问。初始一个空的集合。
两种询问，一种是往集合里加入一个点。一种是从集合里删除已经存在的点。
对于每次询问，输出把集合里的点通过树的边连在一起所须要的最小代价（每条边都有权值）
思路
15年多校第一场的题。比赛的时候没想出来，看了题解算是豁然开朗。首先对这棵树预处理出DFS序。
对集合的操作相当于构造了一棵新的树。
首先我们考虑插入操作。
在已有的集合里寻找DFS序比操作点u大的最小点y以及小于操作点的最大点x。我们能够得到一个结论。联通这三点的路径是必须要加在新构造的树上的。（从x訪问到y之间的路上不会出现集合上的点，加入u后，从x到u，u到y的路上也相同不会有集合上的点）所以我们仅仅须要在现有的答案上加上u点到xy链的距离就可以。
这个距离就要通过求LCA来计算，公式为
dir[u]-dir[lca(x,u)]-dir[lca(y,u)]+dir[lca(x,y)]当找不到这种两个点时，说明操作点的DFS序为最大或者最小。故我们仅仅须要取出集合中DFS序最大和最小的两个点。同上来求就可以。
删除时同理。注意在集合操作时，若加入则在加入前查找，删除则在删除后查找。
AC代码
代码中LCA使用倍增算法。
/*************************************************************************
> File Name: main.cpp
> Author: znl1087
> Mail: loveCJNforever@gmail.com
> Created Time: 日 7/26 13:46:25 2015
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
using namespace std;
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:
",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
",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
",st);
}else{
if(se.find(point(num))==se.end()){
printf("%d
",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
",st);
}
}
}
return 0;
}