Description
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路
径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x y:
在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行m次操作
Input
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述
1<=n,m<=100000
Output
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
Sample Input
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
Sample Output
3
4
2
2
4
2
2
HINT
Source
鸣谢infinityedge上传
Solution
LCT+树链剖分。
Tip:注意找真实的father和son时不能直接用splay中的。Father一开始就要记下来后面可能会改变！Son要找后继一样找！
|
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 161 162 163 164 165 166 167 168 169 170 171 172 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=100010; int n,m,tot,cnt,Next[N<<1],head[N],tree[N<<1],Fa[N],fa[N],dep[N],size[N],Son[N],tid[N],NUM[N],top[N],Max[N*4],lazy[N*4],son[N][2]; void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } void dfs(int u,int father,int depth) { Fa[u]=fa[u]=father;dep[u]=depth;size[u]=1;Son[u]=0; int maxsize=0; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (v==fa[u]) continue; dfs(v,u,depth+1); size[u]+=size[v]; if (size[v]>maxsize) { maxsize=size[v]; Son[u]=v; } } } void dfs1(int u,int ancestor) { tid[u]=++cnt;NUM[cnt]=u;top[u]=ancestor; if (Son[u]) dfs1(Son[u],ancestor); for (int i=head[u];i;i=Next[i]) if (tree[i]!=fa[u]&&tree[i]!=Son[u]) dfs1(tree[i],tree[i]); } void build(int l,int r,int id) { if (l==r) { Max[id]=dep[NUM[l]];return;} int mid=(l+r)>>1; build(l,mid,id<<1); build(mid+1,r,id<<1|1); Max[id]=max(Max[id<<1],Max[id<<1|1]); } void down(int id) { if (lazy[id]!=0) { Max[id<<1]+=lazy[id]; Max[id<<1|1]+=lazy[id]; lazy[id<<1]+=lazy[id]; lazy[id<<1|1]+=lazy[id]; lazy[id]=0; } } void change(int l,int r,int id,int x,int y,int d) { if (l>y||r<x) return; if (l!=r) down(id); if (x<=l&&r<=y) { Max[id]+=d; lazy[id]+=d; return; } int mid=(l+r)>>1; change(l,mid,id<<1,x,y,d); change(mid+1,r,id<<1|1,x,y,d); Max[id]=max(Max[id<<1],Max[id<<1|1]); } int query_max(int l,int r,int id,int x,int y) { if (l>y||r<x) return 0; if (l!=r) down(id); if (x<=l&&r<=y) return Max[id]; int mid=(l+r)>>1; return max(query_max(l,mid,id<<1,x,y),query_max(mid+1,r,id<<1|1,x,y)); } int query_sum(int l,int r,int id,int x) { if (l>x||r<x) return 0; if (l!=r) down(id); if (l==r&&l==x) return Max[id]; int mid=(l+r)>>1; return query_sum(l,mid,id<<1,x)+query_sum(mid+1,r,id<<1|1,x); } int LCA(int x,int y) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); x=Fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); return x; } int Query(int x) { return query_sum(1,n,1,tid[x]); } inline bool isRoot(int x) { return (son[fa[x]][0]!=x)&&(son[fa[x]][1]!=x);} inline void Rotate(int x) { int y=fa[x],z=fa[y],l,r; if (son[y][0]==x) l=0;else l=1; r=l^1; if (!isRoot(y)) { if (son[z][0]==y) son[z][0]=x;else son[z][1]=x; } fa[x]=z;fa[y]=x;fa[son[x][r]]=y; son[y][l]=son[x][r];son[x][r]=y; } inline void splay(int x) { while (!isRoot(x)) { int y=fa[x],z=fa[y]; if (!isRoot(y)) { if ((son[z][0]==y)^(son[y][0]==x)) Rotate(x); else Rotate(y); } Rotate(x); } } inline void access(int x) { for (int i=0;x;i=x,x=fa[x]) { splay(x); if (son[x][1]) { int id=son[x][1]; while (son[id][0]) id=son[id][0]; change(1,n,1,tid[id],tid[id]+size[id]-1,1); } if (i) { int id=i; while (son[id][0]) id=son[id][0]; change(1,n,1,tid[id],tid[id]+size[id]-1,-1); } son[x][1]=i; } } int main() { scanf("%d%d",&n,&m); tot=cnt=0; for (int i=1;i<=n-1;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs(1,0,1); dfs1(1,1); build(1,n,1); while (m--) { int id,x,y; scanf("%d",&id); if (id==1) { scanf("%d",&x);access(x);} if (id==2) { scanf("%d%d",&x,&y);printf("%d\n",Query(x)+Query(y)-Query(LCA(x,y))*2+1);} if (id==3) { scanf("%d",&x);printf("%d\n",query_max(1,n,1,tid[x],tid[x]+size[x]-1));} } return 0; } |
