2286: [Sdoi2011]消耗战

分析
　　虚树练习题。
　　构建虚树，在虚树上DP。
　　跟着gxb学虚-tree。。。
代码
  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <cmath>
  6 #include <cctype>
  7 
  8 using namespace std;
  9 
 10 const int N = 250100; 
 11 const int INF = 1e9;
 12 
 13 int head[N<<1],nxt[N<<1],to[N<<1],w[N<<1],TotE;
 14 int deth[N],val[N],siz[N],dfn[N],fa[N],son[N],bel[N],sk[N<<1],top,Time_index;
 15 int A[N];
 16 
 17 inline int read() {
 18     int x = 0,f = 1;char ch =getchar();
 19     for (; !isdigit(ch); ch=getchar()) if (ch=='-') f=-1;
 20     for (; isdigit(ch); ch=getchar()) x = x*10+ch-'0';
 21     return x * f;
 22 }
 23 bool cmp(const int &a,const int &b) {
 24     return dfn[a] < dfn[b];
 25 }
 26 void Add_edge(int u,int v,int c) {
 27     ++TotE;to[TotE] = v;w[TotE] = c;nxt[TotE] = head[u];head[u] = TotE;
 28     ++TotE;to[TotE] = u;w[TotE] = c;nxt[TotE] = head[v];head[v] = TotE;
 29 }
 30 void add_edge(int u,int v) {
 31     ++TotE;to[TotE] = v;nxt[TotE] = head[u];head[u] = TotE;
 32 }
 33 void dfs1(int u,int mn) {
 34     val[u] = mn;
 35     siz[u] = 1;
 36     for (int i=head[u]; i; i=nxt[i]) {
 37         int v = to[i];
 38         if (v==fa[u]) continue;        
 39         fa[v] = u;
 40         deth[v] = deth[u] + 1;
 41         dfs1(v,min(w[i],mn));
 42         siz[u] += siz[v];
 43         if (!son[u] || siz[v] > siz[son[u]]) son[u] = v;
 44     }
 45 }
 46 void dfs2(int u,int top) {
 47     bel[u] = top;
 48     dfn[u] = ++Time_index;
 49     if (!son[u]) return;
 50     dfs2(son[u],top);
 51     for (int i=head[u]; i; i=nxt[i]) {
 52         int v = to[i];
 53         if (v==fa[u] || v==son[u]) continue;
 54         dfs2(v,v);
 55     }
 56 }
 57 int Lca(int u,int v) {
 58     while (bel[u] != bel[v]) {
 59         if (deth[bel[u]] < deth[bel[v]]) swap(u,v);
 60         u = fa[bel[u]];
 61     }
 62     if (deth[u] < deth[v]) return u;
 63     return v;
 64 }
 65 void Insert(int p) {
 66     int x = sk[top];
 67     if (x==1) {sk[++top] = p;return ;}
 68     int lca = Lca(p,x);
 69     if (lca == x) return; // 此题构建虚树不同的是，若x==lca，不加入p。 
 70     while (lca != x) {
 71         int y = sk[--top];
 72         if (dfn[y] < dfn[lca]) {
 73             add_edge(lca,x);
 74             sk[++top] = lca;
 75             break;
 76         }
 77         add_edge(y,x);
 78         x = sk[top];
 79     }
 80     sk[++top] = p;
 81 }
 82 long long DP(int u) {
 83     if (!head[u]) return val[u];
 84     long long ans = 0;
 85     for (int i=head[u]; i; i=nxt[i]) ans += DP(to[i]);
 86     head[u] = 0;
 87     return min(ans,(long long)val[u]);    
 88 }
 89 int main() {
 90     int n = read();
 91     for (int i=1; i<n; ++i) {
 92         int u = read(),v = read(),w = read();
 93         Add_edge(u,v,w);
 94     }
 95     deth[1] = 1;
 96     dfs1(1,INF);
 97     dfs2(1,1);
 98     TotE = 0;
 99     memset(head,0,sizeof(head));
100     
101     int m = read();
102     while (m--) {
103         TotE = 0;sk[top = 1] = 1;
104         
105         int k = read();
106         for (int i=1; i<=k; ++i) A[i] = read();
107         sort(A+1,A+k+1,cmp);
108         for (int i=1; i<=k; ++i) Insert(A[i]);
109         while (--top) add_edge(sk[top],sk[top+1]);
110         
111         long long ans = 0;
112         for (int i=head[1]; i; i=nxt[i]) ans += DP(to[i]); // 单独处理1的情况，否则val[1]设为很大的longlong数，INF不够。 
113         printf("%lld
",ans);
114         head[1] = 0;        
115     }
116     return 0;
117 }