3611: [Heoi2014]大工程虚树学习

3611: [Heoi2014]大工程

Time Limit: 60 Sec   Memory Limit: 512 MB Submit: 1509   Solved: 643 [ Submit][ Status][ Discuss]

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 

这题算是虚树的入门题了吧，但我觉得消耗战还简单一点

但是消耗战那题难得写了。。

说一下虚树吧

首先在我学习的时候有个重大误区，就是以为虚树是一开始建的

于是大概看了下思想yy了半天什么都没想出来。。。。

于是就开始%%%

忽然发现虚树是对于每一个询问的有用点与他们的LCA来建一个新的树，叫做虚树

可以证明，有用点数k的lca是不超过k-1个的，这个可以看这里

然后呢，跳出这个误区后，问题就比较明朗了

至于建法，我建议直接膜代码就可以了，我倒觉得看代码更好理解一点。。

然后就没什么了。。

代码（很丑）：

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long LL; const LL N=1000005; const LL MAX=1<<30; struct qq{LL x,y,last;}e[N*2];LL num,last[N]; LL n,m; LL mymin (LL x,LL y){return x<y?x:y;} LL mymax (LL x,LL y){return x>y?x:y;} void init (LL x,LL y) { num++; e[num].x=x;e[num].y=y; e[num].last=last[x]; last[x]=num; } LL dep[N],fa[N][22],id[N],cnt; void dfs (LL x,LL ffa) { fa[x][0]=ffa;id[x]=++cnt; for (LL u=1;(1<<u)<=dep[x];u++) fa[x][u]=fa[fa[x][u-1]][u-1]; for (LL u=last[x];u!=-1;u=e[u].last) { LL y=e[u].y; if (y==ffa) continue; dep[y]=dep[x]+1; dfs(y,x); } } LL k; LL h[N]; LL sta[N]; bool cmp (LL a,LL b){return id[a]<id[b];} LL get (LL x,LL y) { if (dep[x]<dep[y]) {LL tt=x;x=y;y=tt;} for (LL u=21;u>=0;u--) if (dep[fa[x][u]]>=dep[y]) x=fa[x][u]; //printf("shen:%lld %lld\n",x,y); if (x==y) return x; for (LL u=21;u>=0;u--) if (fa[x][u]!=fa[y][u]) x=fa[x][u],y=fa[y][u]; return fa[x][0]; } void bt ()//建立虚树 { sort(h+1,h+1+k,cmp); LL cnt=1;sta[cnt]=1; // for (LL u=1;u<=k;u++) printf("%lld ",h[u]); for (LL u=1;u<=k;u++) { if (h[u]==1) continue; LL lca=get(h[u],sta[cnt]); // printf("H:%lld %lld\n",h[u],lca); if (lca==sta[cnt]) sta[++cnt]=h[u]; else { while (true) { LL x=sta[cnt],xx=sta[cnt-1];cnt--; if (xx==lca) { init(xx,x); break; } if (dep[xx]<dep[lca]) { init(lca,x); sta[++cnt]=lca; break; } init(xx,x); } sta[++cnt]=h[u]; } } for (LL u=1;u<cnt;u++) init(sta[u],sta[u+1]); // for (LL u=1;u<=num;u++) printf("lalal:%lld %lld\n",e[u].x,e[u].y); } LL tot[N],lalal[N];//这颗子树有多少人 这颗子树的深度和 LL shen[N],shen1[N];//这一棵子树的最深深度是多少 最浅的深度 LL ans,ans1,ans2;//权值和 最小值 最大值 LL ooo[N],ooo1; void dfs (LL x) { if (ooo[x]==ooo1) {shen[x]=shen1[x]=dep[x];lalal[x]=dep[x];tot[x]=1;} else {shen[x]=-MAX;shen1[x]=MAX;tot[x]=0;lalal[x]=0;} for (LL u=last[x];u!=-1;u=e[u].last) { LL y=e[u].y; dfs(y); ans1=mymin(ans1,shen1[y]+shen1[x]-2*dep[x]); ans2=mymax(ans2,shen[x]+shen[y]-2*dep[x]); shen1[x]=mymin(shen1[x],shen1[y]); shen[x]=mymax(shen[x],shen[y]); tot[x]=tot[x]+tot[y]; lalal[x]+=lalal[y]; } for (LL u=last[x];u!=-1;u=e[u].last) { LL y=e[u].y; ans=ans+(tot[x]-tot[y])*(lalal[y]-dep[x]*tot[y]); } // printf("ooo:%lld %lld %lld %lld\n",x,tot[x],lalal[x],ans); last[x]=-1; } int main() { cnt=num=0;memset(last,-1,sizeof(last)); scanf("%lld",&n); for (LL u=1;u<n;u++) { LL x,y; scanf("%lld%lld",&x,&y); init(x,y);init(y,x); } dep[1]=1;dfs(1,0); /* for (LL u=1;u<=n;u++) printf("%lld ",dep[u]); printf("\n");*/ memset(last,-1,sizeof(last)); memset(ooo,0,sizeof(ooo));ooo1=0; scanf("%lld",&m); while (m--) { ooo1++;num=0; scanf("%lld",&k); for (LL u=1;u<=k;u++) { scanf("%lld",&h[u]); ooo[h[u]]=ooo1; } bt(); ans=0;ans1=MAX;ans2=-MAX; dfs(1); printf("%lld %lld %lld\n",ans,ans1,ans2); } return 0; }