bzoj 2286 [Sdoi2011]消耗战（虚树+树上DP）

【题目链接】

　　http://www.lydsy.com/JudgeOnline/problem.php?id=2286

【题意】

　　给定一棵树，切断一条树边代价为ci，有m个询问，每次问使得1号点与查询的k个点不连通的最小代价。

【思路】

虚树+树上DP。

构建虚树，这里学了一个比较机智的构图方法：当询问点之间存在子孙后代关系时只保留最上面的节点。

在这种构图方式的基础上进行树上DP，设f[u]表示以u为根的子树，则有转移式：

f[u]=min{mn[u] , sum(f[v])},u不是资源点

　　　　　f[u]=mn[u],u是资源点

其中mn[u]表示u到根的路径上的最短边。Ps：每个叶子都代表一个询问点，第二个抉择只是为了提供最短边都在u之下的情况，如果在u之上虽然会出现费用计算重合但这不是最优解所以无关紧要。

需要注意的是mx[1]赋大值，d[1]设为1，对应清空边表而非一次n的循环。另外vector中的clear()并不是释放空间，可以看作形如size=0的操作，所以不用担心初始化时间的问题。

LCA好像写得有点挫，效率不是很高的样子=-=

【代码】

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7  
  8 typedef long long LL;
  9 const int N = 250000+10;
 10 const int D = 20;
 11  
 12 struct Edge{ int u,v,w;
 13 };
 14 vector<Edge> es;
 15 vector<int> g[N],G[N];
 16 int fa[N][D],d[N],dfn[N],bin[D]; LL mx[N];
 17 int n,m,dfsc;
 18  
 19 void adde(int u,int v,int w) {
 20     es.push_back((Edge){u,v,w});
 21     int m=es.size(); g[u].push_back(m-1);
 22 }
 23 void adde2(int u,int v) {
 24     if(u!=v) G[u].push_back(v); else return ;
 25     //printf("es(%d,%d)
",u,v);
 26 }
 27 bool cmp(const int& lhs,const int& rhs) { return dfn[lhs]<dfn[rhs];
 28 }
 29  
 30 void dfs(int u) {
 31     dfn[u]=++dfsc;
 32     for(int i=0;i<g[u].size();i++) {
 33         Edge e=es[g[u][i]]; int v=e.v;
 34         if(v!=fa[u][0]) {
 35             fa[v][0]=u;
 36             for(int j=1;j<D;j++) fa[v][j]=fa[fa[v][j-1]][j-1];
 37             d[v]=d[u]+1; mx[v]=min(mx[u],(LL)e.w);
 38             dfs(v);
 39         }
 40     }
 41 }
 42 int LCA(int u,int v) {
 43     if(d[v]>d[u]) swap(u,v);
 44     for(int i=D-1;i>=0;i--)
 45         if(d[fa[u][i]]>=d[v]) u=fa[u][i];
 46     if(u==v) return u;
 47     for(int i=D-1;i>=0;i--)
 48         if(fa[u][i]!=fa[v][i]) u=fa[u][i] , v=fa[v][i];
 49     return fa[u][0];
 50 }
 51 void read(int &x) {
 52     char c=getchar(); while(!isdigit(c)) c=getchar();
 53     x=0; while(isdigit(c)) x=x*10+c-'0' , c=getchar();
 54 }
 55 LL f[N];
 56 void dp(int u) {
 57     LL tmp=0; 
 58     for(int i=0;i<G[u].size();i++) {
 59         dp(G[u][i]);
 60         tmp += f[G[u][i]];
 61     }
 62     G[u].clear();           //清空边表 
 63     f[u]=mx[u];             //f=mx 所以mx赋大值 
 64     if(tmp && tmp<f[u]) f[u]=tmp;
 65 }
 66 void solve() {
 67     int top=0,tot=0,k;
 68     static int st[N],h[N];
 69     read(k);
 70     for(int i=1;i<=k;i++) read(h[i]) ;
 71     sort(h+1,h+k+1,cmp);
 72     /////////////////////////////////////    以下是一个十分机智的重新构图 from hzwer
 73     h[++tot]=h[1];
 74     for(int i=2;i<=k;i++)
 75         if(LCA(h[tot],h[i])!=h[tot]) h[++tot]=h[i];     //虚树中不会出现询问点间的子孙后代关系
 76     st[++top]=1;
 77     for(int i=1;i<=tot;i++) {
 78         int p=h[i],lca=LCA(p,st[top]);
 79         for(;;) {
 80             if(d[st[top-1]]<=d[lca]) {
 81                 adde2(lca,st[top--]);
 82                 if(st[top]!=lca) st[++top]=lca;
 83                 break;
 84             }
 85             adde2(st[top-1],st[top]); top--;
 86         }
 87         if(st[top]!=p) st[++top]=p;
 88     }
 89     while(--top) adde2(st[top],st[top+1]);
 90     /////////////////////////////////////
 91     dp(1);
 92     printf("%lld
",f[1]);
 93 }
 94  
 95 int main() {
 96     read(n);
 97     int u,v,w;
 98     for(int i=0;i<n-1;i++) {
 99         read(u),read(v),read(w);
100         adde(u,v,w) , adde(v,u,w);
101     }
102     mx[1]=1e18,d[1]=1; dfs(1);      //d[1]=1
103     read(m);
104     while(m--) solve();
105     return 0;
106 }