刷题总结——大工程（bzoj3611）

题目：

Description

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。

我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。

在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。

现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间新建 C(k,2)条新通道。

现在对于每个计划，我们想知道：

1.这些新通道的代价和

2.这些新通道中代价最小的是多少

3.这些新通道中代价最大的是多少

Input

第一行 n 表示点数。

接下来 n-1 行，每行两个数 a,b 表示 a 和 b 之间有一条边。

点从 1 开始标号。接下来一行 q 表示计划数。

对每个计划有 2 行，第一行 k 表示这个计划选中了几个点。

第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。

Output

输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。

Sample Input

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

Sample Output

3 3 3
6 6 6
1 1 1
2 2 2
2 2 2

HINT

n<=1000000

q<=50000并且保证所有k之和<=2*n

题解：

先构造虚树，为了维护答案anssum，ansmin，ansmax我们需要维护每个点i的sonsum[i]，maxdis[i]，mindis[i]，cnt[i]分别表示该点所在子树的所有特殊点到这一点的距离总和，该点所在子树中的一个特殊点到该点距离的最大值以及最小值，和该点所在子树中的特殊点数量和···具体怎么更新三个答案和维护这四个值看代码吧

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N=1e6+;

inline int R()

{

  char c;int f=;

  for(c=getchar();c<''||c>'';c=getchar());

  for(;c<=''&&c>='';c=getchar())

    f=(f<<)+(f<<)+c-'';

  return f;

}

int fst[N],go[N*],nxt[N*],tot,dfn[N],deep[N],g[N][],Cnt;

int vir[N],tag[N],tmp,stack[N],top,vn,tn,par[N];

int n,m,ansmax,ansmin,cnt[N],maxdis[N],mindis[N];

long long anssum,sonsum[N];

inline void comb(int a,int b)

{

  nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b;

  nxt[++tot]=fst[b],fst[b]=tot,go[tot]=a;

}

inline void comb1(int a,int b)

{

  nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b;

}

inline void dfs(int u,int fa)

{

  dfn[u]=++Cnt;

  for(int e=fst[u];e;e=nxt[e])

  {

    int v=go[e];

    if(v==fa)  continue;

    deep[v]=deep[u]+;g[v][]=u;

    dfs(v,u);

  }

}

inline int get(int a,int b)

{

  int i,j;

  if(deep[a]<deep[b])  swap(a,b);

  for(i=;(<<i)<=deep[a];i++);i--;

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

    if(deep[a]-(<<j)>=deep[b])

      a=g[a][j];

  if(a==b)  return a;

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

    if(g[a][i]!=g[b][i])

      a=g[a][i],b=g[b][i];

  return g[a][];

}

inline void pre()

{

  tot=stack[top=]=,tmp++,anssum=,ansmin=1e+,ansmax=;

}

inline bool cmp(int a,int b)

{

  return dfn[a]<dfn[b];

}

inline void build()

{

  sort(vir+,vir+vn+,cmp);

  vn=unique(vir+,vir+vn+)-vir-;tn=vn;

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

  {

    if(!top)

    {

      par[vir[i]]=;stack[++top]=vir[i];fst[stack[top]]=;

      continue;

    }

    int lca=get(vir[i],stack[top]);

    while(deep[stack[top]]>deep[lca])

    {

      if(deep[stack[top-]]<deep[lca])  par[stack[top]]=lca;

      top--;

    }

    if(stack[top]!=lca)

    {

      par[lca]=stack[top];

      vir[++vn]=lca;

      stack[++top]=lca;fst[stack[top]]=;

    }

    stack[++top]=vir[i];fst[stack[top]]=;

    par[vir[i]]=lca;

  }

  sort(vir+,vir+vn+,cmp);

}

inline void dp(int u)

{

  cnt[u]=(tag[u]==tmp?:);sonsum[u]=;

  maxdis[u]=;mindis[u]=(tag[u]==tmp?:1e+);

  for(int e=fst[u];e;e=nxt[e])

  {

    int v=go[e];dp(v);

    ansmin=min(ansmin,mindis[u]+mindis[v]+deep[v]-deep[u]);

    ansmax=max(ansmax,maxdis[u]+maxdis[v]+deep[v]-deep[u]);

    anssum+=(long long)cnt[u]*cnt[v]*(deep[v]-deep[u])+(long long)sonsum[u]*cnt[v]+(long long)sonsum[v]*cnt[u];

    maxdis[u]=max(maxdis[u],maxdis[v]+deep[v]-deep[u]);

    mindis[u]=min(mindis[u],mindis[v]+deep[v]-deep[u]);

    sonsum[u]+=(sonsum[v]+(long long)cnt[v]*(deep[v]-deep[u]));

    cnt[u]+=cnt[v];

  }

}

int main()

{

  freopen("a.in","r",stdin);

  n=R();int a,b;

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

  {

    a=R(),b=R();

    comb(a,b);

  }

  deep[]=;

  dfs(,);

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

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

      g[j][i]=g[g[j][i-]][i-];

  m=R();

  while(m--)

  {

    vn=R();pre();

    for(int i=;i<=vn;i++)  vir[i]=R(),tag[vir[i]]=tmp;

    build();

    for(int i=;i<=vn;i++)  comb1(par[vir[i]],vir[i]);

    dp(vir[]);

    printf("%lld %d %d\n",anssum,ansmin,ansmax);

  }

  return ;

}

巴特西