点击查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e6 + 10;
struct Edge{
struct EDGE{int to,next,w;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v,int w){edge[++cnt] = {v,head[u],w};head[u] = cnt;}
}e1,e2;
int n,q,k,h[N];
int fa[N],dfn[N],dist[N],dep[N],siz[N],top[N],tot,son[N];
bitset<N> Q;
void dfs1(int x){
siz[x] = 1;dep[x] = dep[fa[x]] + 1;dfn[x] = ++tot;
for(int i = e1.head[x]; i;i = e1.edge[i].next){
int y = e1.edge[i].to;
if(y == fa[x]) continue;
dist[y] = dist[x] + 1;
fa[y] = x;dfs1(y);
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
void dfs2(int x,int t){
top[x] = t;
if(son[x]) dfs2(son[x],t);else return;
for(int i = e1.head[x]; i;i = e1.edge[i].next){
int y = e1.edge[i].to;
if(y == fa[x] || y == son[x]) continue;
dfs2(y,y);
}
}
inline int LCA(int x,int y){
int fx = top[x],fy = top[y];
while(fx != fy){
if(dep[fx] < dep[fy]) swap(fx,fy),swap(x,y);
x = fa[fx];
fx = top[x];
}
if(dep[x] > dep[y]) swap(x,y);
return x;
}
inline bool cmp(int x,int y){return dfn[x] < dfn[y];}
vector<int> use;
inline void clear_vtree(){
for(auto i:use) e2.head[i] = 0;
e2.cnt = 0;vector<int> ().swap(use);
rep(i,1,k,1) Q[h[i]] = false;
}
inline void build(){
sort(h + 1,h + 1 + k,cmp);
vector<int> res;
res.emplace_back(1);
rep(i,1,k - 1,1){
res.emplace_back(h[i]);
res.emplace_back(LCA(h[i + 1],h[i]));
}
res.emplace_back(h[k]);
sort(res.begin(),res.end(),cmp);
res.erase(unique(res.begin(),res.end()),res.end());
int len = res.size();
rep(i,0,len-2,1){
int lca = LCA(res[i],res[i + 1]);
e2.add(lca,res[i + 1],dist[res[i + 1]] - dist[lca]);
use.emplace_back(lca);use.emplace_back(res[i + 1]);
}
}
ll f[N],g1[N],g2[N],sz[N],ans1,ans2,ans3;
const ll inf = 9223372036854775806;
void dp(int x){
sz[x] = Q[x];
int res = 0;
for(int i = e2.head[x]; i;i = e2.edge[i].next){
int y = e2.edge[i].to;
res++;
dp(y);
sz[x] += sz[y];
f[x] += f[y] + sz[y]*(e2.edge[i].w);
int res1 = g1[y]+e2.edge[i].w,res2 = g2[y]+e2.edge[i].w;
if(res1 < g1[x]){
g1[x] = res1;
if(res2 < g2[x]) g2[x] = res2;
}
else{if(res1 < g2[x]) g2[x] = res1;}
}
ans1 += (res>1||Q[x])*f[x];
// ans2 = min(ans2,g1[x] + g2[x]);
// ans3 = max(ans3,(g1[x] == LLONG_MAX/2?0:g1[x])+(g2[x]==LLONG_MAX/2?0:g2[x]));
}
inline void solve(){
cin>>n;
rep(i,1,n-1,1){int u,v;cin>>u>>v;e1.add(u,v,1);e1.add(v,u,1);}
dfs1(1);dfs2(1,1);
cin>>q;
while(q--){
cin>>k;
rep(i,1,k,1) cin>>h[i],Q[h[i]] = true;
build();ans1 = 0,ans3 = 0,ans2 = LLONG_MAX;
for(auto i:use) f[i] = sz[i] = 0,g1[i] = g2[i] = LLONG_MAX/2;
dp(1);
rep(i,1,k,1) rep(j,i+1,k,1)
ans2 = min(ans2,0ll+dist[h[j]]+dist[h[i]]-dist[LCA(h[i],h[j])]*2),ans3 = max(0ll+dist[h[i]]+dist[h[j]]-dist[LCA(h[i],h[j])]*2,ans3);
cout<<ans1<<' '<<ans2<<' '<<ans3<<'\n';
clear_vtree();
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}