BZOJ3611 HEOI2014大工程

先建虚树，然后统计答案。

对于这个两点间最大值和最小值的操作我参考了hzwer的代码。

建虚树时注意判自环

By：大奕哥

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e6+;

 struct node{

     int to,nex,w;

 }e[N<<],d[N<<];

 int cnt,dnt,dead[N],head[N],ans1,ans2,id,idx[N],h[N],f[N][],dd[N],q,n,top,size[N];

 bool v[N];long long sum;

 void add(int x,int y,int w)

 {

     e[++cnt].to=y;e[cnt].w=w;e[cnt].nex=head[x];head[x]=cnt;

 }

 void ddd(int x,int y,int w)

 {

     if(x==y)return;

     d[++dnt].to=y;d[dnt].w=w;d[dnt].nex=dead[x];dead[x]=dnt;

 }

 void dfs(int x,int fa)

 {

     for(int i=;i<=;++i)

     f[x][i]=f[f[x][i-]][i-];

     idx[x]=++id;

     for(int i=head[x];i;i=e[i].nex)

     {

         int y=e[i].to;

         if(y==fa)continue;

         f[y][]=x;dd[y]=dd[x]+;

         dfs(y,x);

     }

 }

 int lca(int x,int y)

 {

     if(dd[x]<dd[y])swap(x,y);

     int tmp=dd[x]-dd[y];

     for(int i=;i<=;++i)

     if(tmp&(<<i))x=f[x][i];

     for(int i=;i>=;--i)

     if(f[x][i]!=f[y][i])

     x=f[x][i],y=f[y][i];

     return x==y?x:f[x][];

 }

 long long dp[N];

 int mx[N],mn[N],k,s[N];

 void donggui(int x)

 {

     size[x]=v[x];dp[x]=;

     mn[x]=v[x]?:2e9;

     mx[x]=v[x]?:-2e9;

     for(int i=dead[x];i;i=d[i].nex)

     {

         int y=d[i].to;

         donggui(y);

         sum+=1ll*(dp[x]+1ll*size[x]*d[i].w)*size[y]+1ll*dp[y]*size[x];

         size[x]+=size[y];

         dp[x]+=dp[y]+1ll*size[y]*d[i].w;

         ans1=min(ans1,mn[x]+d[i].w+mn[y]);

         ans2=max(ans2,mx[x]+d[i].w+mx[y]);

         mn[x]=min(mn[x],mn[y]+d[i].w);

         mx[x]=max(mx[x],mx[y]+d[i].w);

     }

     dead[x]=;

 }

 bool cmp(int x,int y)

 {

     return idx[x]<idx[y];

 }

 void solve()

 {

     scanf("%d",&k);

     for(int i=;i<=k;++i)scanf("%d",&h[i]);

     for(int i=;i<=k;++i)v[h[i]]=;

     sort(h+,h++k,cmp);

     top=dnt=;

     s[++top]=;

     for(int i=;i<=k;++i)

     {

         int x=h[i];int ff=lca(x,s[top]);

         if(ff==s[top]){s[++top]=x;continue;}

         while(ff==lca(s[top-],x))

         {

             ddd(s[top-],s[top],dd[s[top]]-dd[s[top-]]);

             top--;ff=lca(s[top],x);

         }

         ddd(ff,s[top],dd[s[top]]-dd[ff]);

         s[top]=ff;s[++top]=x;

     }

     for(int i=;i<top;++i)

     ddd(s[i],s[i+],dd[s[i+]]-dd[s[i]]);

     ans1=2e9;ans2=-2e9;sum=;

     donggui();

     printf("%lld %d %d\n",sum,ans1,ans2);

     for(int i=;i<=k;++i)v[h[i]]=;

     return;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<n;++i)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         add(x,y,);add(y,x,);

     }

     dfs(,);

     scanf("%d",&q);

     while(q--)solve();

     return ;

 }