3991: [SDOI2015]寻宝游戏

https://www.lydsy.com/JudgeOnline/problem.php?id=3991

分析：

　　虚树+set。

　　要求树上许多点之间的路径的总长的2倍。就是虚树。

　　结论：如果将所有的点按dfs序拍好，答案就是相邻点之间的路径长度的和*2。所以这个可以按dfn维护一个set，每次操作查找前驱后继。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int INF = 1e9;

 const int N = ;

 int head[N], nxt[N << ], to[N << ], len[N << ], En;

 int deth[N], bel[N], siz[N], son[N], fa[N], id[N], dfn[N], TimeIndex;

 LL dis[N];

 bool vis[N];

 LL tmp, Ans;

 set<int> s;

 set<int> :: iterator it;

 void add_edge(int u,int v,int w) {

     ++En; to[En] = v; len[En] = w; nxt[En] = head[u]; head[u] = En;

     ++En; to[En] = u; len[En] = w; nxt[En] = head[v]; head[v] = En;

 }

 void dfs1(int u) {

     deth[u] = deth[fa[u]] + ;

     for (int i=head[u]; i; i=nxt[i]) {

         int v = to[i];

         if (v == fa[u]) continue;

         dis[v] = dis[u] + len[i];

         fa[v] = u;

         dfs1(v);

         siz[u] += siz[v];

         if (!son[u] || siz[son[u]] < siz[v]) son[u] = v;

     }

 }

 void dfs2(int u,int top) {

     bel[u] = top;

     dfn[u] = ++TimeIndex; id[TimeIndex] = u;

     if (!son[u]) return ;

     dfs2(son[u], top);

     for (int i=head[u]; i; i=nxt[i]) {

         int v = to[i];

         if (v != fa[u] && v != son[u]) dfs2(v, v);

     }

 }

 int LCA(int u,int v) {

     while (bel[u] != bel[v]) {

         if (deth[bel[u]] < deth[bel[v]]) swap(u, v);

         u = fa[bel[u]];

     }

     return deth[u] < deth[v] ? u : v;

 }

 LL getdis(int x,int y) {

     int lca = LCA(x, y);

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

 }

 void ins(int x) {

     int L = *(--s.lower_bound(dfn[x]));

     int R = *(s.upper_bound(dfn[x]));

     if (L != -INF) Ans += getdis(id[L], x);

     if (R != INF) Ans += getdis(id[R], x);

     if (L != -INF && R != INF) Ans -= getdis(id[L], id[R]);

     s.insert(dfn[x]); vis[x] = ;

 }

 void del(int x) {

     s.erase(dfn[x]); vis[x] = ;

     int L = *(--s.lower_bound(dfn[x]));

     int R = *(s.upper_bound(dfn[x]));

     if (L != -INF) Ans -= getdis(id[L], x);

     if (R != INF) Ans -= getdis(id[R], x);

     if (L != -INF && R != INF) Ans += getdis(id[L], id[R]);

 }

 int main() {

     int n = read(), Q = read();

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

         int u = read(), v = read(), w = read();

         add_edge(u, v, w);

     }

     dfs1();

     dfs2(, );

     s.insert(-INF), s.insert(INF);

     while (Q--) {

         tmp = ;

         int x = read();

         if (!vis[x]) ins(x);

         else del(x);

         if (s.size() > ) {

             it = s.begin();

             int L = *(++it);

             it = s.end();

             int R = *(--(--it));

             tmp = getdis(id[L], id[R]);

         }

         printf("%lld\n",Ans + tmp);

     }

     return ;

 }