「題意」給你一棵樹,每次詢問若在在選中的k個點兩兩連接無相邊,邊權為原來樹上的點對距離,求這些邊的:1)權值和 2)最短的邊 3)最長的邊。所有k之和$\le$2 n。 「分析」虛樹模板題。(但是獨立寫出來還是很振奮人心的合)直接考慮對虛樹dp,設pmn[x]為x到x的子樹內的關鍵點的最短距離,pm ...
「題意」給你一棵樹,每次詢問若在在選中的k個點兩兩連接無相邊,邊權為原來樹上的點對距離,求這些邊的:1)權值和 2)最短的邊 3)最長的邊。所有k之和$\le$2*n。
「分析」虛樹模板題。(但是獨立寫出來還是很振奮人心的合)直接考慮對虛樹dp,設pmn[x]為x到x的子樹內的關鍵點的最短距離,pmx[x]為最長距離,sum[x]為x到子樹內所有關鍵點的距離之和。這些都很好處理。統計答案利用樹形dp的常用技巧——有當前子樹和以前的子樹進行組合。
「實現」
/*
寫對啦!woc
*/
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int n,q,k;
int dfn[N],dep[N],fa[N][20];
vector<int> e[N];
void pre(int x,int pa) {
static int cnt=0;
dfn[x]=++cnt;
dep[x]=dep[fa[x][0]=pa]+1;
for(int i=1; (1<<i)<=dep[x]; ++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(unsigned i=0; i<e[x].size(); ++i)
if(e[x][i]!=pa) pre(e[x][i],x);
}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
int dif=dep[x]-dep[y];
for(int i=19; ~i; --i)
if(dif&(1<<i)) x=fa[x][i];
if(x==y) return x;
for(int i=19; ~i; --i)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int a[N],s[N],top,cnt;
int head[N],to[N<<1],len[N<<1],last[N<<1];
void add_edge(int x,int y,int w) {
to[++cnt]=y;
len[cnt]=w;
last[cnt]=head[x];
head[x]=cnt;
}
bool cmp(int x,int y) {
return dfn[x]<dfn[y];
}
void ist(int x) {
if(top==1) {
if(x!=1) s[++top]=x;
return;
}
int t=lca(s[top],x);
if(t!=s[top]) {
for(; top>1&&dfn[s[top-1]]>=dfn[t]; top--)
add_edge(s[top-1],s[top],dep[s[top]]-dep[s[top-1]]);
if(t!=s[top]) add_edge(t,s[top],dep[s[top]]-dep[t]), s[top]=t;
}
s[++top]=x;
}
bool mark[N];
LL lmn[N],lmx[N],siz[N],sum[N];
LL pum,pmn,pmx;
void dfs(int x) {
lmn[x]=inf;
lmx[x]=-inf;
sum[x]=siz[x]=0;
if(mark[x]) {
lmx[x]=lmn[x]=0;
siz[x]=1;
}
for(int i=head[x]; i; i=last[i]) {
dfs(to[i]);
pmn=min(pmn,lmn[x]+lmn[to[i]]+len[i]);
pmx=max(pmx,lmx[x]+lmx[to[i]]+len[i]);
pum+=sum[x]*siz[to[i]]
+(siz[x]-mark[x])*sum[to[i]]
+(siz[x]-mark[x])*len[i]*siz[to[i]];
lmn[x]=min(lmn[x],lmn[to[i]]+len[i]);
lmx[x]=max(lmx[x],lmx[to[i]]+len[i]);
sum[x]+=sum[to[i]]+siz[to[i]]*len[i];
siz[x]+=siz[to[i]];
}
if(mark[x]) pum+=sum[x];
head[x]=0;
mark[x]=0;
}
void print() {
printf("asphaush tree: \n");
static queue<int> Q;
Q.push(1);
while(!Q.empty()) {
int x=Q.front(); Q.pop();
for(int i=head[x]; i; i=last[i]) {
printf("%d -> %d, length is %d\n",x,to[i],len[i]);
Q.push(to[i]);
}
}
}
void solve() {
//printf("\nnew solving case: \n");
scanf("%d",&k);
for(int i=1; i<=k; ++i) {
scanf("%d",&a[i]);
mark[a[i]]=true;
}
sort(a+1,a+k+1,cmp);
cnt=0;
s[top=1]=1;
for(int i=1; i<=k; ++i) ist(a[i]);
for(; top>1; top--)
add_edge(s[top-1],s[top],dep[s[top]]-dep[s[top-1]]);
// print();
pum=0;
pmn=inf;
pmx=-inf;
dfs(1);
printf("%lld %lld %lld\n",pum,pmn,pmx);
}
int main() {
scanf("%d",&n);
for(int x,y,i=n; --i; ) {
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
pre(1,0);
scanf("%d",&q);
while(q--) solve();
return 0;
}
/*
10
2 1
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
5
2
5 4
2
10 4
2
5 2
2
6 1
2
6 1
*/