3611: [Heoi2014]大工程

分析：
　　树形dp+虚树。
　　首先建立虚树，在虚树上dp。
　　dp：sum[i]为i的子树中所有询问点之间的和。siz[i]为i的子树中有多少询问点，mn[i]为i的子树中询问点到根的最小距离，mx为i的子树中询问点到根的最大距离。
　　具体过程见 https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p4103
代码：
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<iostream>
  6  
  7 using namespace std;
  8  
  9 const int N = 1000100;
 10 const int INF = 1e9;
 11  
 12 int head[N<<1],to[N<<1],nxt[N<<1];
 13 int siz[N],deth[N],fa[N],son[N],dfn[N],bel[N],sk[N],tag[N];
 14 int mn[N],mx[N],val[N],A[N]; 
 15 long long sum[N],Sum;
 16 int Time_index,Min,Max,TotE,top; 
 17  
 18 inline int read() {
 19     int x = 0,f = 1;char ch = getchar();
 20     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;
 21     for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
 22     return x * f;
 23 }
 24 bool cmp_dfn(const int &a,const int &b) {
 25     return dfn[a] < dfn[b];
 26 }
 27 void Add_edge(int u,int v) {
 28     ++TotE; to[TotE] = v; nxt[TotE] = head[u]; head[u] = TotE;
 29     ++TotE; to[TotE] = u; nxt[TotE] = head[v]; head[v] = TotE; 
 30 }
 31 void add_edge(int u,int v) {
 32     ++TotE; to[TotE] = v; val[TotE] = deth[v]-deth[u]; nxt[TotE] = head[u]; head[u] = TotE;
 33 }
 34 void dfs1(int u) {
 35     siz[u] = 1; 
 36     deth[u] = deth[fa[u]] + 1; // 1的深度设为1。 
 37     for (int i=head[u]; i; i=nxt[i]) {
 38         int v = to[i];
 39         if (v==fa[u]) continue;
 40         fa[v] = u;
 41         dfs1(v);
 42         siz[u] += siz[v];
 43         if (!son[u] || siz[son[u]] < siz[v]) 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(x,p);
 69     while (lca != x) {
 70         int y = sk[--top];
 71         if (dfn[y] < dfn[lca]) {
 72             add_edge(lca,x);sk[++top] = lca; // !!!
 73             break;
 74         }
 75         add_edge(y,x);x = sk[top];
 76     }
 77     sk[++top] = p;
 78 }
 79 void DP(int u) {
 80     if (tag[u]) mx[u] = mn[u] = 0,sum[u] = 0,siz[u] = 1;
 81     else mn[u] = INF,mx[u] = -INF,sum[u] = 0,siz[u] = 0;
 82     for (int i=head[u]; i; i=nxt[i]) {
 83         int v = to[i];
 84         DP(v);
 85         Min = min(Min,mn[u]+mn[v]+val[i]); mn[u] = min(mn[u],mn[v]+val[i]);
 86         Max = max(Max,mx[u]+mx[v]+val[i]); mx[u] = max(mx[u],mx[v]+val[i]);
 87         Sum += 1ll*siz[u]*(sum[v]+val[i]*siz[v])+1ll*siz[v]*sum[u]; //!!!
 88         sum[u] += sum[v]+val[i]*siz[v];
 89         siz[u] += siz[v];
 90     }
 91     tag[u] = head[u] = 0;
 92 }
 93 int main () {
 94      
 95     int n = read();
 96     for (int i=1; i<n; ++i) {
 97         int u = read(),v = read();
 98         Add_edge(u,v);
 99     }
100      
101     dfs1(1);
102     dfs2(1,1);
103      
104     memset(head,0,sizeof(head));
105      
106     int m = read();
107     while (m--) {
108         TotE = 0;top = 0;sk[++top] = 1;
109          
110         int k = read();
111         for (int i=1; i<=k; ++i) A[i] = read(),tag[A[i]] = true;
112         sort(A+1,A+k+1,cmp_dfn);
113          
114         if (A[1] != 1) sk[++top] = A[1]; // 防止1加入两边。        
115         for (int i=2; i<=k; ++i) Insert(A[i]);
116         while (--top) add_edge(sk[top],sk[top+1]);
117          
118         Sum = 0,Min = INF,Max = -INF;
119         DP(1);
120         printf("%lld %d %d
",Sum,Min,Max);
121     }
122      
123     return 0;
124 }