会构建虚树之后就是noip提高组的题目了

稍微难一点的是求代价和，只要注意按一个方向避免重复计算贡献即可

1 const inf=100000000;  2 type node=record  3        po,next:longint;  4      end;  5   6 var mi,mx,fa,p,q,size,d,a,b:array[0..1000010] of longint;  7     e:array[0..2000010] of node;  8     f:array[0..1000010] of int64;  9     v:array[0..1000010] of boolean; 10     anc:array[0..1000010,0..21] of longint; 11     ans2,ans3,z,t,h,i,len,n,m,s,j,x,y:longint; 12     dis,ans1:int64; 13  14 procedure add(x,y:longint); 15   begin 16     inc(len); 17     e[len].po:=y; 18     e[len].next:=p[x]; 19     p[x]:=len; 20   end; 21  22 procedure swap(var a,b:longint); 23   var c:longint; 24   begin 25     c:=a; 26     a:=b; 27     b:=c; 28   end; 29  30 function max(a,b:longint):longint; 31   begin 32     if a>b then exit(a) else exit(b); 33   end; 34  35 function min(a,b:longint):longint; 36   begin 37     if a>b then exit(b) else exit(a); 38   end; 39  40 procedure dfs(x:longint); 41   var i,y:longint; 42   begin 43     inc(h); 44     a[x]:=h; 45     i:=p[x]; 46     while i<>0 do 47     begin 48       y:=e[i].po; 49       if fa[x]<>y then 50       begin 51         fa[y]:=x; 52         anc[y,0]:=x; 53         d[y]:=d[x]+1; 54         dfs(y); 55       end; 56       i:=e[i].next; 57     end; 58   end; 59  60 procedure sort(l,r:longint); 61   var i,j,x:longint; 62   begin 63     i:=l; 64     j:=r; 65     x:=a[b[(l+r) shr 1]]; 66     repeat 67       while a[b[i]]
      
       j) then 70       begin 71         swap(b[i],b[j]); 72         inc(i); 73         dec(j); 74       end; 75     until i>j; 76     if l
       
        d[y] then 87       for i:=p downto 0 do 88         if d[x]-1 shl i>=d[y] then x:=anc[x,i]; 89     if x=y then exit(x); 90     for i:=p downto 0 do 91       if (anc[y,i]<>anc[x,i]) then 92       begin 93         x:=anc[x,i]; 94         y:=anc[y,i]; 95       end; 96     exit(fa[x]); 97   end; 98  99 procedure dp(x:longint);100   var i,y:longint;101   begin102     f[x]:=0;103     if v[x] then104     begin105       size[x]:=1;  //size[]表示虚树中包含的关键点个数106       mi[x]:=0;    107       mx[x]:=0;108     end109     else begin110       size[x]:=0;111       mi[x]:=inf;112       mx[x]:=-inf;113     end;114     i:=p[x];115     while i<>0 do116     begin117       y:=e[i].po;118       dp(y);119       dis:=d[y]-d[x];120       ans1:=ans1+(f[x]+int64(size[x])*dis)*int64(size[y])+f[y]*int64(size[x]);121       size[x]:=size[x]+size[y];122       f[x]:=f[x]+f[y]+int64(size[y])*dis;123       ans2:=min(ans2,mi[x]+dis+mi[y]);124       ans3:=max(ans3,mx[x]+dis+mx[y]);125       mx[x]:=max(mx[x],dis+mx[y]);126       mi[x]:=min(mi[x],dis+mi[y]);127       i:=e[i].next;128     end;129     p[x]:=0;130   end;131 132 begin133   readln(n);134   for i:=1 to n-1 do135   begin136     readln(x,y);137     add(x,y);138     add(y,x);139   end;140   dfs(1);141   t:=trunc(ln(n)/ln(2));142   for  i:=1 to t do 143     for j:=1 to n do 144     begin145       y:=anc[j,i-1];146       if  y<>0 then anc[j,i]:=anc[y,i-1];147     end;148   fillchar(p,sizeof(p),0);149   readln(m);150   for i:=1 to m do151   begin152     readln(s);153     for j:=1 to s do154     begin155       read(b[j]);156       v[b[j]]:=true;157     end;158     readln;159     sort(1,s);160     ans1:=0;161     ans2:=inf;162     ans3:=0;163     len:=0;164     t:=1;165     q[1]:=1;166     for j:=1 to s do167     begin168       x:=b[j];169       z:=lca(x,q[t]);170       while d[z]
        
         =d[q[t-1]] then173         begin174           add(z,q[t]);175           dec(t);176           if q[t]<>z then177           begin178             inc(t);179             q[t]:=z;180           end;181           break;182         end;183         add(q[t-1],q[t]);184         dec(t);185       end;186       if q[t]<>x then187       begin188         inc(t);189         q[t]:=x;190       end;191     end;192     while t>1 do193     begin194       add(q[t-1],q[t]);195       dec(t);196     end;197     dp(1);198     writeln(ans1,' ',ans2,' ',ans3);199     for j:=1 to s do200       v[b[j]]:=false;201   end;202 end.