解题：SDOI 2011 消耗战

题面

本身求答案是简单的树上DP，只需要求出根到每个点路径上的最小值，然后考虑割连父亲的边还是割所有儿子即可，但是每次都这样做一次显然不能通过，考虑优化

用虚树来优化：虚树是针对树上一些点建出来的一棵树，上面只有这些点和它们的LCA。显然这样虚树的大小不会超过2*所选点数，这样在缩小了问题规模的同时还保留了原树的性质。

具体的建法：

0.预处理DFS序

1.将所选点按DFS序从小到大排序

2.用栈维护一条从根延伸下来的链，依次将排序后的点nde加入。若栈为空则直接入栈，否则设栈顶为top：

3.求nde和top的lca，讨论：

①lca是top，将nde入栈，跑路

②lca不是top，设栈顶起第二个元素为sec。在lca的DFS序不大于sec时不断将sec与top相连并弹栈

(1)如果lca的DFS序小于top，将lca与top相连，弹栈

(2)如果lca仍然不是top，将lca入栈

(3)将nde入栈

(因为我们按DFS序排序，所以lca不可能是nde)

4.将所有点加入后，不断将sec与top相连并弹栈，直到栈里只有一个元素，这就是虚树的树根

之后就可以愉快地树形DP辣

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=500005;
  6 int T,n,m,t1,t2,t3,cnt,Cnt,tot,poi;
  7 int P[N],Noww[N],Goal[N],p[N],noww[N],goal[N],val[N],cut[N];
  8 int siz[N],far[N],dep[N],imp[N],top[N],dfn[N],pts[N],stk[N];
  9 long long mini[N];
 10 bool cmp(int a,int b)
 11 {
 12     return dfn[a]<dfn[b];
 13 }
 14 void Link(int f,int t,int v)
 15 {
 16     noww[++cnt]=p[f],p[f]=cnt;
 17     goal[cnt]=t,val[cnt]=v;
 18     noww[++cnt]=p[t],p[t]=cnt;
 19     goal[cnt]=f,val[cnt]=v;
 20 }
 21 void Linka(int f,int t)
 22 {
 23     Noww[++Cnt]=P[f];
 24     Goal[Cnt]=t,P[f]=Cnt;
 25 }
 26 void DFS(int nde,int fth,int dth)
 27 {
 28     int tmp=0;
 29     siz[nde]=1,far[nde]=fth,dep[nde]=dth;
 30     for(int i=p[nde];i;i=noww[i])
 31         if(goal[i]!=fth)
 32         {
 33             mini[goal[i]]=min(mini[nde],1ll*val[i]);
 34             DFS(goal[i],nde,dth+1);
 35             siz[nde]+=siz[goal[i]];
 36             if(siz[goal[i]]>tmp)
 37                 tmp=siz[goal[i]],imp[nde]=goal[i];
 38         }
 39 }
 40 void Mark(int nde,int tpp)
 41 {
 42     top[nde]=tpp,dfn[nde]=++tot;
 43     if(imp[nde])
 44     {
 45         Mark(imp[nde],tpp);
 46         for(int i=p[nde];i;i=noww[i])
 47             if(goal[i]!=far[nde]&&goal[i]!=imp[nde])        
 48                 Mark(goal[i],goal[i]);
 49     }
 50 }
 51 int LCA(int x,int y)
 52 {
 53     while(top[x]!=top[y])
 54     {
 55         if(dep[top[x]]<dep[top[y]])
 56             swap(x,y); x=far[top[x]];
 57     }
 58     return dep[x]<dep[y]?x:y;
 59 }
 60 void Insert(int nde)
 61 {
 62     if(!poi) stk[++poi]=nde;
 63     else
 64     {
 65         int lca=LCA(nde,stk[poi]);
 66         if(lca!=stk[poi]) 
 67         {
 68             while(poi>1&&dfn[lca]<=dfn[stk[poi-1]])    
 69                 Linka(stk[poi-1],stk[poi]),poi--;
 70             if(dfn[lca]<dfn[stk[poi]])
 71                 Linka(lca,stk[poi]),poi--;
 72             if(lca!=stk[poi])        
 73                 stk[++poi]=lca;
 74         }
 75         stk[++poi]=nde;
 76     }
 77 }
 78 long long Getans(int nde)
 79 {
 80     long long tmp=0;
 81     for(int i=P[nde];i;i=Noww[i])
 82         tmp+=Getans(Goal[i]); P[nde]=0;
 83     return cut[nde]?mini[nde]:min(mini[nde],tmp);
 84 }
 85 int main()
 86 {
 87     scanf("%d",&n);
 88     for(int i=1;i<n;i++)
 89         scanf("%d%d%d",&t1,&t2,&t3),Link(t1,t2,t3);
 90     for(int i=1;i<=n;i++) mini[i]=1e12;
 91     DFS(1,0,1),Mark(1,1); 
 92     scanf("%d",&T);
 93     while(T--)
 94     {
 95         scanf("%d",&m),Cnt=poi=0;
 96         for(int i=1;i<=m;i++) scanf("%d",&pts[i]);
 97         sort(pts+1,pts+1+m,cmp);
 98         for(int i=1;i<=m;i++) Insert(pts[i]),cut[pts[i]]=true;
 99         while(poi>1) Linka(stk[poi-1],stk[poi]),poi--;
100           printf("%lld
",Getans(stk[1]));
101         for(int i=1;i<=m;i++) cut[pts[i]]=false;
102     }
103     return 0;
104 }

View Code