http://www.lydsy.com/JudgeOnline/problem.php?id=3991
虚树
虚树是什么？
虚树就是在一棵原树中，有若干个特定的结点，求另外一棵虚树，虚树一定包含特定点，当然可能还有其他的非特定点，但是虚树中的点的父子关系要与原树中的点的父子关系相对应。
构建虚树很简单，其实就是按照在原树中的DFS序插入即可。
回归原题。
我们发现一些结论：
出发点的一定是有宝藏的；
结合虚树的形态理解，最优方案中的到达的点的DFS序一定是从小到大的。
知道这个结论就很简单了，我们用一个set维护有宝藏的点，并以DFS序为关键字从小到大排序。
插入和删除一个点就是在set中找前驱和后驱，然后维护一下答案即可。
#include<cstdio> #include<cstdlib> #include<iostream> #include<fstream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<utility> #include<set> #include<bitset> #include<vector> #include<functional> #include<deque> #include<cctype> #include<climits> #include<complex> //#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL; typedef double DB; typedef pair<int,int> PII; typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a)) #define mmcy(a,b) memcpy(a,b,sizeof(a)) #define fill(a,l,r,v) fill(a+l,a+r+1,v) #define re(i,a,b) for(i=(a);i<=(b);i++) #define red(i,a,b) for(i=(a);i>=(b);i--) #define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++) #define fi first #define se second #define m_p(a,b) make_pair(a,b) #define p_b(a) push_back(a) #define SF scanf #define PF printf #define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;} template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;} template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-9; inline int sgn(DB x){if(abs(x)<EPS)return 0;return(x>0)?1:-1;} const DB Pi=acos(-1.0); inline int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } inline LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } const int maxN=100000; int N,Q; int now,first[maxN+100]; struct Tedge{int v,next,cost;}edge[2*maxN+100]; inline void addedge(int u,int v,int cost) { now++; edge[now].v=v; edge[now].cost=cost; edge[now].next=first[u]; first[u]=now; } int id[maxN+100]; int head,tail,que[maxN+100]; int size[maxN+100],jump[maxN+100][31]; int dep[maxN+100]; LL len[maxN+100]; inline void BFS() { int i,j; dep[que[head=tail=1]=1]=1; len[1]=0; jump[1][0]=1;re(j,1,30)jump[1][j]=jump[jump[1][j-1]][j-1]; while(head<=tail) { int u=que[head++],v,cost; for(i=first[u],v=edge[i].v,cost=edge[i].cost;i!=-1;i=edge[i].next,v=edge[i].v,cost=edge[i].cost)if(v!=jump[u][0]) { dep[que[++tail]=v]=dep[u]+1; len[v]=len[u]+LL(cost); jump[v][0]=u;re(j,1,30)jump[v][j]=jump[jump[v][j-1]][j-1]; } } red(j,tail,1) { int u=que[j],v; size[u]=1; for(i=first[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)if(v!=jump[u][0])size[u]+=size[v]; } id[1]=1; re(j,1,tail) { int u=que[j],v,temp=0; for(i=first[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)if(v!=jump[u][0]) { id[v]=id[u]+temp+1; temp+=size[v]; } } } inline void swim(int &x,int H){int i;for(i=0;H;H>>=1,i++)if(H&1)x=jump[x][i];} inline int ask_LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); swim(x,dep[x]-dep[y]); if(x==y)return x; int i; red(i,30,0)if(jump[x][i]!=jump[y][i])x=jump[x][i],y=jump[y][i]; return jump[x][0]; } inline LL dis(int x,int y) { int lca=ask_LCA(x,y); return len[x]+len[y]-2*len[lca]; } struct Tdata { int pos,id; inline Tdata(int _pos=0,int _id=0){pos=_pos;id=_id;} inline bool operator <(Tdata B)const{return id<B.id;} }; set<Tdata>S; #define iter set<Tdata>::iterator LL ans; int f[maxN+100]; int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); int i; N=gint();Q=gint(); now=-1;mmst(first,-1); re(i,1,N-1) { int x=gint(),y=gint(),z=gint(); addedge(x,y,z); addedge(y,x,z); } BFS(); ans=0; while(Q--) { int t=gint(); if(!f[t]) { f[t]=1; S.insert(Tdata(t,id[t])); iter a=S.find(Tdata(t,id[t])),pre,suc; pre=a;if(a==S.begin())pre=S.end();else pre--; suc=a;suc++; if(pre!=S.end() && suc!=S.end())ans-=dis(pre->pos,suc->pos); if(pre!=S.end())ans+=dis(pre->pos,a->pos); if(suc!=S.end())ans+=dis(a->pos,suc->pos); } else { iter a=S.find(Tdata(t,id[t])),pre,suc; pre=a;if(a==S.begin())pre=S.end();else pre--; suc=a;suc++; if(pre!=S.end() && suc!=S.end())ans+=dis(pre->pos,suc->pos); if(pre!=S.end())ans-=dis(pre->pos,a->pos); if(suc!=S.end())ans-=dis(a->pos,suc->pos); f[t]=0; S.erase(Tdata(t,id[t])); } if(S.size()==0) PF("%I64d ",ans); else { iter L=S.begin(),R=S.end();R--; PF("%I64d ",ans+dis(R->pos,L->pos)); } } return 0; }