[2015hdu多校联赛补题]hdu5296 Annoying problem

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5296

题意：给你一棵n个结点的边权树和一个树上点的集合，开始时集合为空

然后进行两种操作：

1、如果结点u不在集合中，那么将u加入集合

2、如果结点u在集合中，那么删除u

每次操作后输出包含点集合的最小联通子图的边权和

题解：

其实问题的本质就是求结点u与子图的距离（如果在子图内部距离为0），yy一下可以想到，若x、y为集合中与u最近的两点，那么dis（u，子图）=dis（u，联通u、x、y三点的汇点）

问题转化为求x、y，将树上结点以dfs序重标号，如果u在点集标号集的外侧，那么x、y分别为点集标号集的最大标号与最小标号，如果在内侧，那么x、y分别为u的左右

然后求u与联通u、x、y三点汇点的距离：

dis（u，联通u、x、y三点的汇点）=（dis（u，x）+dis（u，y）+dis（x，y））/2-dis（x，y）

dis（a，b）=dfn[a] +dfn[b] -2dfn[lca(a，b)] （lca和dfn都是求树链长度用到的东西，lca（a，b）：a、b的最近公共祖先，dfn[x]：根结点到x的路径的边权和）

  1 /*
  2  * Problem: 
  3  * Author:  SHJWUDP
  4  * Created Time:  2015/8/2 星期日 15:20:01
  5  * File Name: 233.cpp
  6  * State: 
  7  * Memo: 
  8  */
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13 #include <vector>
 14 #include <set>
 15 
 16 using namespace std;
 17 
 18 struct Edge {
 19     int u, v, w;
 20     Edge(int u, int v, int w):u(u), v(v), w(w){}
 21 };
 22 
 23 int n, q;
 24 vector<Edge> edges;
 25 vector<vector<int> > G;
 26 vector<int> pos, id, dep, dfn;
 27 vector<vector<int> > fa;
 28 set<int> S;
 29 int root, cnt;
 30 void init(int sz) {
 31     edges.clear();
 32     G.assign(sz, vector<int>(0));
 33     S.clear();
 34     pos.resize(sz);
 35     id.resize(sz);
 36     dep.resize(sz);
 37     dfn.resize(sz);
 38     fa.assign(sz, vector<int>(20));
 39 }
 40 void addEdge(int u, int v, int w) {
 41     edges.push_back(Edge(u, v, w));
 42     G[u].push_back(edges.size()-1);
 43 }
 44 void dfs(int u) {
 45     pos[u]=++cnt;
 46     id[cnt]=u;
 47     for(int k=1; k<20; k++) {
 48         fa[u][k]=fa[fa[u][k-1]][k-1];
 49     }
 50     for(int i : G[u]) {
 51         Edge & e=edges[i];
 52         if(e.v==fa[u][0]) continue;
 53         dfn[e.v]=dfn[u]+e.w;
 54         dep[e.v]=dep[u]+1;
 55         fa[e.v][0]=u;
 56         dfs(e.v);
 57     }
 58 }
 59 int lca(int u, int v) {
 60     if(dep[u]<dep[v]) swap(u, v);
 61     for(int k=19; k>=0; k--) {
 62         if(dep[fa[u][k]]>=dep[v]) {
 63             u=fa[u][k];
 64         }
 65     }
 66     if(u==v) return u;
 67     for(int k=19; k>=0; k--) {
 68         if(fa[u][k]!=fa[v][k]) {
 69             u=fa[u][k]; v=fa[v][k];
 70         }
 71     }
 72     return fa[u][0];
 73 }
 74 int func(int u) {
 75     int res=0;
 76     if(!S.empty()) {
 77         auto it=S.lower_bound(pos[u]);
 78         int x, y;
 79         if(it==S.begin() || it==S.end()) {
 80             x=id[*S.begin()];
 81             y=id[*S.rbegin()];
 82         } else {
 83             x=id[*it];
 84             y=id[*--it];
 85         }
 86         res=dfn[u]-dfn[lca(u, x)]-dfn[lca(u, y)]+dfn[lca(x, y)];
 87     }
 88     return res;
 89 }
 90 int main() {
 91 #ifndef ONLINE_JUDGE
 92     freopen("in", "r", stdin);
 93     //freopen("out", "w", stdout);
 94 #endif
 95     int T, now=0;
 96     scanf("%d", &T);
 97     while(T--) {
 98         scanf("%d%d", &n, &q);
 99         init(n+1);
100         for(int i=0; i<n-1; i++) {
101             int a, b, c;
102             scanf("%d%d%d", &a, &b, &c);
103             addEdge(a, b, c);
104             addEdge(b, a, c);
105         }
106         root=1; cnt=0; fa[root][0]=root; dep[root]=0; dfn[root]=0; dfs(root);
107         printf("Case #%d:
", ++now);
108         int ans=0;
109         while(q--) {
110             int op, u;
111             scanf("%d%d", &op, &u);
112             auto it=S.find(pos[u]);
113             if(op==1 && it==S.end()) {
114                 ans+=func(u);
115                 S.insert(pos[u]);
116             } else if(op==2 && it!=S.end()) {
117                 S.erase(it);
118                 ans-=func(u);
119             }
120             printf("%d
", ans);
121         }
122     }
123     return 0;
124 }

hdu 5296