YZOJ P4578 [CSP-S 2019 四校联训 Round 1]树上排列
时间限制：4000MS 内存限制：524288KB
难度：\(7.0\)
-
题目描述
给定一颗 \(n\) 个点的树。每个点都一个正整数点权 \(A_i\)，你需要支持以下两种操作：
1、询问点 \(x\) 和点 \(y\) 之间的路径上的所有点（包括点 \(x\) 和点 \(y\) ）的点权是否构成一个从 \(1\) 开始的排列。
2、将 \(A_x\) 修改为 \(y\)。
-
输入格式
第一行一个正整数 \(T\) 表示数据组数。
接下来一行输入两个正整数 \(n,q\) 表示数的点数和询问个数。
接下来一行 \(n\) 个正整数，第 \(i\) 个正整数表示 \(A_i\) 的初值。
接下来 \(n-1\) 行每行两个正整数 \(u,v\) 表示树上的一条边 \((u,v)\) 。
接下来 \(n\) 行每行三个正整数 \(tp,x,y\) 表示一个操作，其中 \(tp\) 表示操作种类。
-
输出格式
对于每一个操作 \(1\) 如果符合条件，输出 Yes ，否则输出 No 。
-
样例输入
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
1 10 5 1 2 3 4 5 6 7 8 9 10 1 2 1 3 2 4 2 5 3 9 4 10 5 6 5 7 5 8 1 4 3 1 10 3 2 10 5 1 10 3 1 5 3 |
-
样例输出
|
1 2 3 4 |
Yes No Yes No |
-
数据规模与约定
保证 \(1 \leq T \leq 10\)，\(1 \leq n,q \leq 2.5 \times 10^5\)，\(1 \leq \sum n,\sum q \leq 5 \times 10^5\)，\(1 \leq u,v,x,y,A_i \leq n\)，\(1 \leq tp \leq 2\)。
Source：Codechef LTIME73A QRYLAND
其实是水题。
注意到 \(1\) 到 \(len\) 的排列是始终不变的，所以可以直接预处理，现在只需要判断两个点权的集合是否相等。
容易想到异或 hash，对于每个 \(a_i\) 都随一个权值，记 \(f_i\) 为 \(i\) 到根路径上权值的异或和，树状数组维护 dfn 即可。
|
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 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <ctime> #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } int a[255050],wN,w[250505]; #define _lowbit(_x) ((_x)&-(_x)) int N,f[250505]; inline void updatef(register int pos,const int&val) { while(pos<=N) f[pos]^=val,pos+=_lowbit(pos); } inline int queryf(register int pos) { register int ans=0; while(pos) ans^=f[pos],pos-=_lowbit(pos); return ans; } int gcnt,ghead[250505],gnext[505050],gnode[505050]; inline void InsertLine(register int s,register int t) { gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t; gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s; } int depth[250505],father[250505],size[250505],son[250505],top[250505]; void DFS0(register int o) { size[o]=1; for(register int j=ghead[o],t;j;j=gnext[j]) if((t=gnode[j]) != father[o]) { depth[t]=depth[o]+1,father[t]=o; DFS0(t); size[o]+=size[t]; (size[t]>size[son[o]] ? son[o]=t : 0); } } int dfcnt,dfn[250505]; void DFS1(register int o) { dfn[o]=++dfcnt; if(o==son[father[o]]) top[o]=top[father[o]]; else top[o]=o; for(register int j=ghead[o],t;j;j=gnext[j]) if((t=gnode[j]) != father[o]) DFS1(t); updatef(dfn[o],w[a[o]]),updatef(dfn[o]+size[o],w[a[o]]); } inline int GetLCA(register int x,register int y) { while(top[x] != top[y]) if(depth[top[x]] > depth[top[y]]) x=father[top[x]]; else y=father[top[y]]; return (depth[x]<depth[y] ? x : y); } int pxw[250505]; int main() { srand(time(NULL)); register int _T=getnum(),mxa=0; while(_T--) { register int N=getnum(),Q=getnum(); ::N=N; for(register int i=1;i<=N;i++) a[i]=getnum(),mxa=_max(mxa,a[i]); for(register int i=wN+1;i<=mxa;i++) w[i]=rand(),pxw[i]=pxw[i-1]^w[i]; wN=_max(wN,mxa); gcnt=0,memset(ghead,0,sizeof(ghead)); for(register int i=1;i<=N-1;i++) InsertLine(getnum(),getnum()); dfcnt=0,memset(son,0,sizeof(son)); memset(f,0,sizeof(f)); DFS0(1),DFS1(1); for(register int lp=1;lp<=Q;lp++) { register int tp=getnum(),x=getnum(),y=getnum(); if(tp==1) { register int lca=GetLCA(x,y); register int ans=queryf(dfn[x])^queryf(dfn[y])^w[a[lca]]; if(ans==pxw[depth[x]+depth[y]-(depth[lca]<<1)+1]) putchar('Y'),putchar('e'),putchar('s'); else putchar('N'),putchar('o'); putchar('\n'); } else { updatef(dfn[x],w[a[x]]),updatef(dfn[x]+size[x],w[a[x]]); a[x]=y; updatef(dfn[x],w[a[x]]),updatef(dfn[x]+size[x],w[a[x]]); } } } return 0; } |