P4103

发表于 分类于
[HEOI2014]大工程

[HEOI2014]大工程

首先是建虚树，记录一下根节点，不多说了。

因为虚树上某些节点不是关键节点，所以不能单纯找树的直径或者最小边什么的。

还是要 DP 的。。。

第一小问的 DP 应该不用多说，就是统计子树内关键节点的数量一个乘法原理就好了。

第二小问的 DP 是求最短距离，设 $g(u)$ 为 $u$ 到其子树内的关键节点的距离最小是多少。然后就是考虑把最小和次小接起来成为一条路径丢给答案比较就完了。

第三小问的 DP 和第二小问基本相同，设 $f(u)$ 是 $u$ 到其子树内的关键节点的最大距离。然后同样是次大与最大接起来。

时间复杂度 $O (\sum k \log n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=4e6,inf=(1ll<<31)-1;

ll n,k,tot,tc,cnt,ans1,ans2,ans3,rt,rt_;
ll h[N+5],flg[N+5],f[N+5],g[N+5];
ll ver[N+5],nxt[N+5],head[N+5],dt[N+5];
ll vc[N+5],nc[N+5],hc[N+5],wc[N+5],dc[N+5];
ll siz[N+5],fa[N+5],hs[N+5],top[N+5],id[N+5],st[N+5];

inline void Dfs(ll p,ll fath) {
  dt[p]=dt[fath]+1;siz[p]=1;fa[p]=fath;
  for(ll i=head[p];i;i=nxt[i]) {
    if(ver[i]==fath) continue;
    Dfs(ver[i],p);siz[p]+=siz[ver[i]];
    if(siz[ver[i]]>siz[hs[p]]) hs[p]=ver[i];
  }
}

inline void Dfs_(ll p,ll fath,ll topf) {
  id[p]=++cnt;top[p]=topf;
  if(hs[p]) Dfs_(hs[p],p,topf);
  for(ll i=head[p];i;i=nxt[i]) {
    if(ver[i]==fath||ver[i]==hs[p]) continue;
    Dfs_(ver[i],p,ver[i]);
  }
}

inline ll Getlca(ll x,ll y) {
  while(top[x]!=top[y]) {
    if(dt[top[x]]<dt[top[y]]) swap(x,y);x=fa[top[x]];
  }
  return dt[x]<dt[y]?x:y;
}

inline ll Askpath(ll x,ll y) {
  ll res=0;
  while(top[x]!=top[y]) {
    if(dt[top[x]]<dt[top[y]]) swap(x,y);
    res+=id[x]-id[top[x]]+1;x=fa[top[x]];
  }
  if(id[x]>id[y]) swap(x,y);res+=id[y]-id[x]+1;
  return res-1;
}

inline void Addedge(ll u,ll v) {
  ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline void Addc(ll u,ll v) {
  vc[++tc]=v;nc[tc]=hc[u];wc[tc]=Askpath(u,v);hc[u]=tc;
}

inline bool cmp(ll x,ll y) {return id[x]<id[y];}

inline void Build() {
  sort(h+1,h+k+1,cmp);ll top=1;
  st[top]=h[1];tc=0;hc[h[1]]=0;
  for(ll i=2,lca;i<=k;i++) {
    lca=Getlca(h[i],st[top]);
    if(lca!=st[top]) {
      while(id[lca]<id[st[top-1]]) {
        Addc(st[top-1],st[top]);Addc(st[top],st[top-1]);top--;
      }
      if(id[lca]>id[st[top-1]]) {
        hc[lca]=0;Addc(lca,st[top]);Addc(st[top],lca);
        st[top]=lca;
      }
      else {Addc(lca,st[top]);Addc(st[top],lca);top--;}
    }
    hc[h[i]]=0;st[++top]=h[i];
  }
  rt=st[1];
  for(ll i=1;i<top;i++) {
    Addc(st[i],st[i+1]);Addc(st[i+1],st[i]);
  }
}

inline void DP(ll p,ll fath) {
  f[p]=0;g[p]=inf;siz[p]=flg[p];
  for(ll i=hc[p];i;i=nc[i]) {
    if(vc[i]==fath) continue;
    DP(vc[i],p);siz[p]+=siz[vc[i]];
    if(flg[vc[i]]||f[vc[i]]) f[p]=max(f[p],f[vc[i]]+wc[i]);
    if(flg[vc[i]]) g[p]=min(g[p],wc[i]);
    if(g[vc[i]]<inf) g[p]=min(g[p],g[vc[i]]+wc[i]);
  }
  if(flg[p]) {
    ans2=min(ans2,g[p]);ans3=max(ans3,f[p]);
  }
  ll ma=0,cma=0,mi=inf,cmi=inf;
  for(ll i=hc[p];i;i=nc[i]) {
    if(vc[i]==fath) continue;
    if(flg[vc[i]]||f[vc[i]]) {
      ll tmp=f[vc[i]]+wc[i];
      if(tmp>=ma) {cma=ma;ma=tmp;}
      else {if(tmp>cma) cma=tmp;}
    }
    if(flg[vc[i]]) {
      ll tmp=wc[i];
      if(tmp<=mi) {cmi=mi;mi=tmp;}
      else {if(tmp<cmi) cmi=tmp;}
    }
    if(g[vc[i]]) {
      ll tmp=g[vc[i]]+wc[i];
      if(tmp<=mi) {cmi=mi;mi=tmp;}
      else {if(tmp<cmi) cmi=tmp;}
    }
  }
  if(cmi<inf) ans2=min(ans2,mi+cmi);
  if(cma>0) ans3=max(ans3,ma+cma);
}

inline void DP_(ll p,ll fath) {
  for(ll i=hc[p];i;i=nc[i]) {
    if(vc[i]==fath) continue;
    DP_(vc[i],p);
    ans1+=wc[i]*siz[vc[i]]*(siz[rt]-siz[vc[i]]);
  }
}

int main() {

  n=read();

  for(ll i=1;i<n;i++) {
    ll u,v;
    u=read();v=read();Addedge(u,v);Addedge(v,u);
  }

  Dfs(1,0);Dfs_(1,0,1);

  ll T;T=read();

  while(T--) {
    ans1=0;ans2=inf;ans3=0;
    k=read();for(ll i=1;i<=k;i++) {h[i]=read();flg[h[i]]=1;}
    Build();DP(rt,0);DP_(rt,0);
    writes(ans1);writes(ans2);writeln(ans3);
    for(ll i=1;i<=k;i++) {flg[h[i]]=0;}
  }

  return 0;
}