bzoj 3611: [Heoi2014]大工程

时间:2023-03-08 18:15:43
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 2000009
#define inf 0x7ffffff
#define ll long long
using namespace std;
int n,head[M],next[M],u[M],cnt,head1[M],next1[M],u1[M],fa[M][],deep[M],m,dfn[M],T,v[M];
int h[M],st[M],mn[M],mx[M],size[M],mx1,mi1,v1[M];
ll cn1,sum[M];
void jia(int a1,int a2)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
return;
}
void jia2(int a1,int a2)
{
if(a1==a2)
return;
cnt++;
next1[cnt]=head1[a1];
head1[a1]=cnt;
u1[cnt]=a2;
v1[cnt]=deep[a2]-deep[a1];
return;
}
bool cmp(int a1,int a2)
{
return dfn[a1]<dfn[a2];
}
void dfs(int a1)
{
dfn[a1]=++T;
for(int i=;(<<i)<=deep[a1];i++)
fa[a1][i]=fa[fa[a1][i-]][i-];
for(int i=head[a1];i;i=next[i])
if(fa[a1][]!=u[i])
{
deep[u[i]]=deep[a1]+;
fa[u[i]][]=a1;
dfs(u[i]);
}
return;
}
int lca(int a1,int a2)
{
if(deep[a1]<deep[a2])
swap(a1,a2);
int a3=deep[a1]-deep[a2];
for(int i=;i<=;i++)
if(a3&(<<i))
a1=fa[a1][i];
for(int i=;i>=;i--)
if(fa[a1][i]!=fa[a2][i])
{
a1=fa[a1][i];
a2=fa[a2][i];
}
if(a1==a2)
return a1;
return fa[a1][];
}
void dp(int x){
sum[x]=;
mx[x]=v[x]?:-inf;
mn[x]=v[x]?:inf;
size[x]=v[x];
for(int i=head1[x];i;i=next1[i]){
int v=u1[i];
dp(v);
cn1+=(sum[x]+size[x]*v1[i])*size[v]+size[x]*sum[v];
size[x]+=size[v];
sum[x]+=sum[v]+(ll)size[v]*v1[i];
mi1=min(mi1,mn[v]+mn[x]+v1[i]);
mx1=max(mx1,mx[v]+mx[x]+v1[i]);
mn[x]=min(mn[x],mn[v]+v1[i]);
mx[x]=max(mx[x],mx[v]+v1[i]);
}
head1[x]=;
}
void solve(){
cnt=cn1=;mi1=inf;mx1=-inf;
int K;
scanf("%d",&K);
for(int i=;i<=K;i++) scanf("%d",&h[i]),v[h[i]]=;
sort(h+,h+K+,cmp);int top=;st[]=;
for(int i=;i<=K;i++){
int now=h[i],f=lca(st[top],now);
if(dfn[f]==dfn[st[top]]) st[++top]=now;
else{
while(top){
int q=st[top-];
if(dfn[q]>dfn[f]) jia2(st[top-],st[top]),top--;
else if(dfn[q]==dfn[f]){
jia2(q,st[top]);top--;break;
}
else {
jia2(f,st[top]);st[top]=f;break;
}
}
if(st[top]!=now) st[++top]=now;
}
}
while(--top)jia2(st[top],st[top+]);
dp();
printf("%lld ",cn1);
printf("%d %d\n",mi1,mx1);
for(int i=;i<=K;i++) v[h[i]]=;
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int a1,a2;
scanf("%d%d",&a1,&a2);
jia(a1,a2);
jia(a2,a1);
}
dfs();
scanf("%d",&m);
for(int i=;i<=m;i++)
solve();
return ;
}

虚树,树形DP