bzoj 3572 [Hnoi2014]世界树

bzoj 3572 [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

10 2 1 3 2 4 3 5 4 6 1 7 3 8 3 9 4 10 1 5 2 6 1 5 2 7 3 6 9 1 8 4 8 7 10 3 5 2 9 3 5 8 Sample Output

1 9 3 1 4 1 1 10 1 1 3 5 4 1 3 1 1 HINT

N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000

点数太多 直接暴力做 每次复杂度是n*m不可接受 考虑建出虚树来处理

将每次询问的点读进来 建虚树 然后预处理每个关键点到哪个关键点最近

用两遍dfs处理下即可 先从所有节点的子节点尝试转移 然后再从所有节点的父节点向子节点 倒着转移一遍即可 然后考虑几种情况 对于虚树上的两个点来说如x,y且设x是y的父节点 那么首先用倍增的方法找到y属于x的哪个子树该节点设为z 然后如果x,y的最近关键点相同就将size[z]-size​​y​​直接加到x的关键点里即可 注意一开始还需要储存一个l数组表示这个关键点一开始管辖多少个子节点 随着不停的删除子节点 我这个节点管辖的点会越来越少 对于这个点剩下的这些点在后面统一处理即可

如果这两个点的关键点不相同 那么我就在中间的链上二分一个点使得这个点以下的点都属于y 即到y最近 然后上面的点到x最近 分别加一下答案即可 复杂度n*log(n)^2

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if(T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=300030;struct node{ int y,next;}data1[N<<1],data[N<<1];int h[N],q[N],size[N],fa[N][20],dep[N],Log[N],num,top,bl[N],l[N],ans[N],h1[N],a[N],b[N];int cnt,dfn[N],Q,n;inline void dfsinit(int x){ size[x]=1;dfn[x]=++cnt; for (int i=h1[x];i;i=data1[i].next){ int y=data1[i].y;if (y==fa[x][0]) continue;fa[y][0]=x;dep[y]=dep[x]+1; for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1]; dfsinit(y);size[x]+=size[y]; }}inline bool cmp(const int &a,const int &b){return dfn[a]dis1||dis2==dis1&&(bl[y]>bl[x])) bl[y]=bl[x];dfs2(y); }}inline void calc(int x,int y){ int z=y;int dis=dep[y]-dep[x]; for (int i=Log[dis];~i;--i) if (dep[fa[z][i]]>dep[x]) z=fa[z][i];l[x]-=size[z]; if (bl[x]==bl[y]){ans[bl[x]]+=size[z]-size[y];return;}int md=y; for (int i=Log[dis];~i;--i){ int f=fa[md][i]; int dis1=calc_dis(f,bl[y]),dis2=calc_dis(f,bl[x]); if (dis1bl[y]) md=fa[md][i]; }ans[bl[x]]+=size[z]-size[md];ans[bl[y]]+=size[md]-size[y];}inline void solve(){ int m=read();for (int i=1;i<=m;++i) a[i]=b[i]=read(),bl[b[i]]=a[i]; sort(a+1,a+m+1,cmp);q[top=1]=1;num=0; for (int i=1;i<=m;++i){ int t=lca(q[top],a[i]); while(top>1){ if (dep[t]>=dep[q[top-1]]) { if (t!=q[top]) insert1(t,q[top]);--top; if (t!=q[top])q[++top]=t;break; }insert1(q[top-1],q[top]);--top; }if (a[i]!=q[top]) q[++top]=a[i]; }int x=q[1];for (int i=2;i<=top;++i) insert1(x,q[i]),x=q[i]; top=0;dfs(1);dfs1(1);dfs2(1); for (int i=1;i<=top;++i) for (int j=h[q[i]];j;j=data[j].next) calc(q[i],data[j].y); for (int i=1;i<=top;++i) ans[bl[q[i]]]+=l[q[i]]; for (int i=1;i<=m;++i) printf("%d,ans[b[i]]);puts(""); for (int i=1;i<=top;++i) bl[q[i]]=h[q[i]]=ans[bl[q[i]]]=0;}int main(){ freopen("bzoj3572.in","r",stdin); n=read();Log[0]=-1;for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。