「BZOJ3572」[HNOI2014] 世界树
Description
世界树是一棵无比巨大的树,它伸出的枝干构成了整个世界。在这里,生存着各种各样的种族和生灵,他们共同信奉着绝对公正公平的女神艾莉森,在他们的信条里,公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述:世界树中有n个种族,种族的编号分别从1到n,分别生活在编号为1到n的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为1。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地a和b之间有道路,b和c之间有道路,因为每条道路长度为1而且又不可能出现环,所卧a与c之间的距离为2。
出于对公平的考虑,第i年,世界树的国王需要授权m[i]个种族的聚居地为临时议事处。对于某个种族x(x为种族的编号),如果距离该种族最近的临时议事处为y(y为议事处所在聚居地的编号),则种族x将接受y议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则y为其中编号最小的临时议事处)。
现在国王想知道,在q年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。
Input
第一行为一个正整数n,表示世界树中种族的个数。
接下来n-l行,每行两个正整数x,y,表示x聚居地与y聚居地之间有一条长度为1的双
向道路。接下来一行为一个正整数q,表示国王询问的年数。
接下来q块,每块两行:
第i块的第一行为1个正整数m[i],表示第i年授权的临时议事处的个数。
第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]],表示被授权为临时议事处的聚居地编号(保证互不相同)。
Output
输出包含q行,第i行为m[i]个整数,该行的第j(j=1,2…,,m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。
Sample Input
21
32
43
54
61
73
83
94
10 1
5
2
61
5
27369
1
8
4
87103
5
29358
Sample Output
19
31411
10
1135
41311
HINT
N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000
题解
构建虚树以后两遍dp处理出虚树上每个点最近的议事处
然后枚举虚树上每一条边,考虑其对两端点的答案贡献
可以用倍增二分出分界点
如果a,b的分界点为mid,a,b路径上a的第一个儿子为x
则对a的贡献是size[x]-size[mid]
对b的贡献是size[mid]-size[b]
还要算上没被考虑的点
嘴上AC还是很简单的。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 300005 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[20]; int n,m,q,cnt,dfn; int fa[N][20],dep[N],last[N],id[N],size[N]; int a[N],b[N],f[N]; int top,s[N],c[N]; int rem[N],bel[N]; struct edge{ int to,next,v; }e[2*N]; bool cmp(int a,int b) { return id[a]<id[b]; } void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; } void dfs(int x,int f) { id[x]=++dfn;size[x]=1; for(int i=1;bin[i]<=dep[x];i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=last[x];i;i=e[i].next) if(e[i].to!=f) { fa[e[i].to][0]=x; dep[e[i].to]=dep[x]+1; dfs(e[i].to,x); size[x]+=size[e[i].to]; } } int lca(int x,int y) { if(dep[x]>dep[y])swap(x,y); int t=dep[y]-dep[x]; for(int i=0;bin[i]<=t;i++) if(bin[i]&t)y=fa[y][i]; for(int i=18;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return x==y?x:fa[x][0]; } int dis(int a,int b) { return dep[a]+dep[b]-2*dep[lca(a,b)]; } void solve(int a,int b) { int x=b,mid=b; for(int i=18;i>=0;i--) if(dep[fa[x][i]]>dep[a])x=fa[x][i]; rem[a]-=size[x]; if(bel[a]==bel[b]) { f[bel[a]]+=size[x]-size[b]; return; } for(int i=18;i>=0;i--) { int nxt=fa[mid][i]; if(dep[nxt]<=dep[a])continue; int t1=dis(bel[a],nxt),t2=dis(bel[b],nxt); if(t1>t2||(t1==t2&&bel[b]<bel[a]))mid=nxt; } f[bel[a]]+=size[x]-size[mid]; f[bel[b]]+=size[mid]-size[b]; } void dfs1(int x) { c[++dfn]=x;rem[x]=size[x]; for(int i=last[x];i;i=e[i].next) { dfs1(e[i].to); if(!bel[e[i].to])continue; int t1=dis(bel[e[i].to],x),t2=dis(bel[x],x); if((t1==t2&&bel[e[i].to]<bel[x])||t1<t2||!bel[x]) bel[x]=bel[e[i].to]; } } void dfs2(int x) { for(int i=last[x];i;i=e[i].next) { int t1=dis(bel[x],e[i].to),t2=dis(bel[e[i].to],e[i].to); if((t1==t2&&bel[e[i].to]>bel[x])||t1<t2||!bel[e[i].to]) bel[e[i].to]=bel[x]; dfs2(e[i].to); } } void query() { top=dfn=cnt=0; m=read(); for(int i=1;i<=m;i++)a[i]=b[i]=read(); for(int i=1;i<=m;i++)bel[a[i]]=a[i]; sort(a+1,a+m+1,cmp); if(bel[1]!=1)s[++top]=1; for(int i=1;i<=m;i++) { int t=a[i],f=0; while(top>0) { f=lca(s[top],t); if(top>1&&dep[f]<dep[s[top-1]]) insert(s[top-1],s[top]),top--; else if(dep[f]<dep[s[top]]) { insert(f,s[top]);top--;break; } else break; } if(s[top]!=f)s[++top]=f; s[++top]=t; } while(top>1)insert(s[top-1],s[top]),top--; dfs1(1);dfs2(1); for(int i=1;i<=dfn;i++) for(int j=last[c[i]];j;j=e[j].next)solve(c[i],e[j].to); for(int i=1;i<=dfn;i++)f[bel[c[i]]]+=rem[c[i]]; for(int i=1;i<=m;i++)printf("%d ",f[b[i]]);puts(""); for(int i=1;i<=dfn;i++) f[c[i]]=bel[c[i]]=last[c[i]]=rem[c[i]]=0; } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); insert(v,u); } dfs(1,0); memset(last,0,sizeof(last)); q=read(); while(q--)query(); return 0; } |
感谢黄学长
ORZ