• 树链剖分入门指南大全

    最近认真学了一下树剖（重链剖分），这里简单记录一些心得

    目录

    原理：

    入门：

    换根操作

    边权下放点权

    区间覆盖

    进阶 

    原理：

    很多情况下我们需要在树上处理一些路径问题，比如叶子到根节点的路径最大子段和之类的，有时候还要加入修改操作，这时候树剖就是一个非常强有力的武器。对于每一个节点a，定义重儿子为其儿子节点中对应子树最大的儿子，重链为以a为起点的一条链，链中的每一个节点都是一个相应节点的重儿子。如图，红色为重儿子，蓝色路径为重链（还是很好理解的）当然，对于叶子节点来说，它自己本身就是一条重链。

     如此来看，每一个节点都会属于一条重链，那么我们就可以在许多条链上来处理问题了。对于路径相关的问题，我们就可以在链之间切换。

    如何每一个节点对应的重链？递归找它的重儿子以及重儿子的重儿子等即可。

    如何找重儿子？dfs一遍并记录最大的子树大小即可。

    这里我们还顺便记录了深度dep【】

    其中son【】就是代表每一个节点的重儿子，没有重儿子的话，son自然记为0

    fa【】代表父亲节点，siz【】代表子树大小（显然）

    1. void init_dfs(ll id,ll p,ll depth)
    2. {
    3. 	dep[id]=depth;
    4. 	siz[id]=1;
    5. 	fa[id]=p;
    6. 	ll son_val=0;
    7. 	for(int i=head[id];i!=-1;i=edge[i].next)
    8. 	{
    9. 		ll y=edge[i].t;
    10. 		if(y==p) continue;
    11. 		init_dfs(y,id,depth+1);
    12. 		siz[id]+=siz[y];
    13. 		if(siz[y]>son_val)
    14. 		{
    15. 			son_val=siz[y];
    16. 			son[id]=y;
    17. 		}
    18. 	}
    19. }

    为了快速在重链之间跳转，我们需要记录每一个节点所在重链的起点，记为top【】，很明显重链的top是能不断向下传递记录的，对于轻儿子，它自己是一条重链的起点，所以从它开始top要改变。这里的idx数组记录的是每一个节点的dfn序，因为我们最后是要解决线性问题（路径），那么给他们一个编号就会方便很多。 此外，为了保证重链节点的dfn序的连续性，我们会优先递归重儿子。

    1. void dfs2(ll id,ll p)//节点编号，对应重链的起点
    2. {
    3. 	top[id]=p;
    4. 	idx[id]=++cnt;
    5. 	a[cnt]=mas[id];
    6. 	if(!son[id]) return;//如果没有重儿子就退出
    7. 	dfs2(son[id],p);//先递归重儿子，top为p
    8. 	for(int i=head[id];i!=-1;i=edge[i].next)
    9. 	{
    10. 		ll y=edge[i].t;
    11. 		if(!idx[y]) dfs2(y,y);//自己是重链的起点，top记为自己
    12. 	}
    13. }

    到这里其实就没了，我们就已经成功地把这棵树剖成一条一条链了。

    但是为了处理各种各样的区间问题，我们还会引入线段树。利用上文的idx数组，我们发现可以成功地把树上路径转为一维区间，那么就可以维护很多东西了，并且线段树构造与一般的并无区别。这里就不贴了。

    还有问题就是查询以及修改。

    如果是路径修改/查询的话：

    我们自然就是在路径经过的一条条重链上进行处理。

    对于每一条需要操作的重链，它是一段连续区间，这是线段树可以解决的问题，那么我们的思路就是让两个点不断跳重链并更新路径上的信息，最后来到同一条重链（top【】值相同）时再修改/查询一次就可以了。

    如果是子树修改/查询的话：

    子树的dfn序是连续的，所以这就是一个简单的线段树操作（大部分情况下）；

    下面以求树上路径和为例给出模板

    1. ll tree_sum(ll x,ll y)//树上路径和 
    2. {
    3. 	ll ans=0;
    4. 	while(top[x]!=top[y])
    5. 	{
    6. 		if(dep[top[x]]swap(x,y);
    7. 		ans=(ans+sum(1,idx[top[x]],idx[x]))%mod;
    8. 		x=fa[top[x]];
    9. 	}
    10. 	if(dep[x]>dep[y]) swap(x,y);
    11. 	//来到同一重链 
    12. 	ans=(ans+sum(1,idx[x],idx[y]))%mod;
    13. 	return ans;
    14. }
    15.  
    16. void tree_add(ll x,ll y,ll val)
    17. {
    18. 	
    19. 	while(top[x]!=top[y])
    20. 	{
    21. 		if(dep[top[x]]swap(x,y);
    22. 		add(1,idx[top[x]],idx[x],val);
    23. 		x=fa[top[x]];
    24. 	}
    25. 	if(dep[x]>dep[y]) swap(x,y);
    26. 	//来到同一重链
    27. 	add(1,idx[x],idx[y],val); 
    28. }
    29.  
    30. void trson_add(ll x,ll val)//以x为根的子树所有权值+=val 
    31. {
    32. 	add(1,idx[x],idx[x]+siz[x]-1,val%mod);
    33. }
    34.  
    35. ll trson_sum(ll x)
    36. {
    37. 	return sum(1,idx[x],idx[x]+siz[x]-1);
    38. }

    这就是树剖基础。

    入门：

    板子题

    换根操作

    大意：

    唯一的难处就是换根操作，但其实这个跟普通的换根dp的思想也是一样的，无非就是考虑根改变了之后对其它查询/操作的影响。

    首先，换根对路径操作肯定是没有影响的（显然）

    考虑其对子树操作的影响：

    令root为当前根，x为要求的根，lca为两者的lca

    1.u==root：直接输出整棵树的和就可以了

    2.lca!=x:x的子树没有变，就正常查询就可以了

    3.lca==x:x的子树就变成了x到root路径上第一个儿子的子树的补集（想一想），这时我们找到这个儿子，并求出它的子树和，再用全局和减去它即可。

    求lca：

    1. ll get_lca(ll x,ll y)//获取两节点的lca 
    2. {
    3. 	while(top[x]!=top[y])
    4. 	{
    5. 		if(dep[top[x]]swap(x,y);
    6. 		x=fa[top[x]];
    7. 	}
    8. 	return dep[x]>dep[y]?y:x;
    9. }

    求路径上的第一个儿子：

    1. ll find_firson(ll x,ll y)//找到x到y路径上的第一个儿子
    2. {
    3.     while(top[x]!=top[y])
    4. 	{
    5. 		if(dep[top[x]]swap(x,y);
    6. 		if(fa[top[x]]==y) return top[x];
    7. 		x=fa[top[x]];
    8. 	}	
    9. 	if(dep[x]swap(x,y);
    10. 	return son[y];
    11. }

    code：

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. inline int read()
    7. {
    8. 	int X=0; bool flag=1; char ch=getchar();
    9. 	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    10. 	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    11. 	if(flag) return X;
    12. 	return ~(X-1);
    13. }
    14. ll n,m,rt,fir,sec,op,x,y,z;
    15. struct ty{
    16. 	ll t,l,next;
    17. }edge[N<<1];
    18. struct tree
    19. {
    20. 	ll l,r;
    21. 	ll val;
    22. 	ll add;//lazy 
    23. 	ll siz; 
    24. }tr[N<<2];
    25. ll cn=0;
    26. ll head[N];
    27. void add(ll a,ll b,ll c)
    28. {
    29. 	edge[++cn].t=b;
    30. 	edge[cn].l=c;
    31. 	edge[cn].next=head[a];
    32. 	head[a]=cn;
    33. }
    34.  
    35. ll dep[N];//节点深度
    36. ll fa[N];//节点父亲
    37. ll son[N];//节点重儿子
    38. ll siz[N];//节点子树的大小
    39. ll mas[N],a[N];//初始序列   处理后的序列
    40. ll cnt=0;//dfs序的计数器
    41. ll idx[N];//节点的dfs序 id 
    42. ll top[N];//节点所在链的顶端 要在init_dfs处理之后才能更新这个 
    43.  
    44. void init_dfs(ll id,ll p,ll depth)//节点 父亲 深度 
    45. {//更新重儿子以及各节点的子树大小&深度 
    46. 	dep[id]=depth;
    47. 	fa[id]=p;
    48. 	siz[id]=1;
    49. 	ll son_val=0;//重儿子的子树大小
    50. 	for(int i=head[id];i!=-1;i=edge[i].next)
    51. 	{
    52. 		ll y=edge[i].t;
    53. 		if(y==p) continue;
    54. 		init_dfs(y,id,depth+1);
    55. 		siz[id]+=siz[y];//子树大小更新 
    56. 		if(siz[y]>son_val)
    57. 		{
    58. 			son_val=siz[y];
    59. 			son[id]=y;
    60. 		}
    61.     } 
    62. } 
    63.  
    64. void dfs2(ll id,ll p)
    65. {
    66. 	idx[id]=++cnt;
    67. 	a[cnt]=mas[id];//序列转移
    68. 	top[id]=p;
    69. 	if(!son[id]) return;//无重儿子的情况(也就是无儿子，是叶子节点)直接返回
    70. 	//下面的dfs顺序：先遍历重儿子，再遍历轻儿子 
    71. 	dfs2(son[id],p);//顶端idx不变
    72. 	for(int i=head[id];i!=-1;i=edge[i].next)
    73. 	{
    74. 		ll y=edge[i].t;
    75. 		if(!idx[y]) dfs2(y,y);//新的链(轻链) 
    76. 	} 
    77. }
    78.  
    79. void push_up(ll p)
    80. {
    81. 	tr[p].val=(tr[p<<1].val+tr[p<<1|1].val);
    82. }
    83.  
    84. void build(ll p,ll l,ll r)
    85. {
    86. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    87. 	if(l==r)
    88. 	{
    89. 		tr[p].val=a[l];//用新的序列值 
    90. 		return;
    91. 	}
    92. 	ll mid=l+r>>1;
    93. 	build(p<<1,l,mid);
    94. 	build(p<<1|1,mid+1,r);
    95. 	push_up(p);
    96. }
    97.  
    98. void push_down(ll p)
    99. {
    100. 	if(tr[p].add==0) return;
    101. 	tr[p<<1].val=(tr[p<<1].val+tr[p<<1].siz*tr[p].add);
    102. 	tr[p<<1|1].val=(tr[p<<1|1].val+tr[p<<1|1].siz*tr[p].add);
    103. 	tr[p<<1].add=(tr[p<<1].add+tr[p].add);
    104. 	tr[p<<1|1].add=(tr[p<<1|1].add+tr[p].add);
    105. 	tr[p].add=0;//下传结束 
    106. }
    107.  
    108. void add(ll p,ll l,ll r,ll val)
    109. {
    110. 	if(tr[p].l>=l&&tr[p].r<=r)
    111. 	{
    112. 		tr[p].val=(tr[p].val+tr[p].siz*val);
    113. 		tr[p].add=(tr[p].add+val);
    114. 		return;
    115. 	}
    116. 	push_down(p);
    117. 	ll mid=tr[p].l+tr[p].r>>1;
    118. 	if(l<=mid) add(p<<1,l,r,val);
    119. 	if(r>=mid+1) add(p<<1|1,l,r,val);
    120. 	push_up(p);
    121. }
    122.  
    123. ll sum(ll p,ll l,ll r)
    124. {
    125. 	ll ans=0;
    126. 	if(tr[p].l>=l&&tr[p].r<=r) return tr[p].val;
    127. 	push_down(p);
    128. 	ll mid=tr[p].l+tr[p].r>>1;
    129. 	if(l<=mid) ans=(ans+sum(p<<1,l,r));
    130. 	if(r>=mid+1) ans=(ans+sum(p<<1|1,l,r));
    131. 	return ans;
    132. }
    133.  
    134. ll tree_sum(ll x,ll y)//树上路径和 
    135. {
    136. 	ll ans=0;
    137. 	while(top[x]!=top[y])
    138. 	{
    139. 		if(dep[top[x]]swap(x,y);
    140. 		ans=(ans+sum(1,idx[top[x]],idx[x]));
    141. 		x=fa[top[x]];
    142. 	}
    143. 	if(dep[x]>dep[y]) swap(x,y);
    144. 	//来到同一重链 
    145. 	ans=(ans+sum(1,idx[x],idx[y]));
    146. 	return ans;
    147. }
    148.  
    149. void tree_add(ll x,ll y,ll val)
    150. {
    151. 	
    152. 	while(top[x]!=top[y])
    153. 	{
    154. 		if(dep[top[x]]swap(x,y);
    155. 		add(1,idx[top[x]],idx[x],val);
    156. 		x=fa[top[x]];
    157. 	}
    158. 	if(dep[x]>dep[y]) swap(x,y);
    159. 	//来到同一重链
    160. 	add(1,idx[x],idx[y],val); 
    161. }
    162.  
    163. ll get_lca(ll x,ll y)//获取两节点的lca 
    164. {
    165. 	while(top[x]!=top[y])
    166. 	{
    167. 		if(dep[top[x]]swap(x,y);
    168. 		x=fa[top[x]];
    169. 	}
    170. 	return dep[x]>dep[y]?y:x;
    171. }
    172.  
    173. ll find_firson(ll x,ll y)//找到x到y路径上的第一个儿子
    174. {
    175.     while(top[x]!=top[y])
    176. 	{
    177. 		if(dep[top[x]]swap(x,y);
    178. 		if(fa[top[x]]==y) return top[x];
    179. 		x=fa[top[x]];
    180. 	}	
    181. 	if(dep[x]swap(x,y);
    182. 	return son[y];
    183. } 
    184.  
    185. void trson_add(ll x,ll val)//以x为根的子树所有权值+=val 
    186. {
    187. 	if(x==rt)
    188. 	{
    189. 		add(1,1,n,val);
    190. 		return;
    191. 	}
    192. 	//
    193. 	ll LCA=get_lca(x,rt);
    194. 	if(LCA!=x) 
    195. 	{
    196. 		add(1,idx[x],idx[x]+siz[x]-1,val);
    197. 		return;
    198. 	}
    199. 	//
    200. 	ll child=find_firson(x,rt);
    201. 	add(1,1,n,val);
    202. 	add(1,idx[child],idx[child]+siz[child]-1,-val);
    203. 	
    204. }
    205.  
    206. ll trson_sum(ll x)
    207. {
    208. 	if(x==rt) return sum(1,1,n);
    209. 	///
    210. 	ll LCA=get_lca(x,rt);
    211. 	if(LCA!=x) return sum(1,idx[x],idx[x]+siz[x]-1);
    212. 	///
    213. 	ll child=find_firson(x,rt);
    214. 	ll res=sum(1,1,n);//整棵树的总和
    215. 	ll f_res=sum(1,idx[child],idx[child]+siz[child]-1);
    216. 	return res-f_res; 
    217. }
    218.  
    219.  
    220. int main()
    221. {
    222. 	memset(head,-1,sizeof head);
    223. 	n=read();
    224. 	rt=1;
    225. 	for(int i=1;i<=n;++i) mas[i]=read();
    226. 	for(int i=1;i
    227. 	{
    228. 		fir=read();
    229. 		add(fir,i+1,1);
    230. 		add(i+1,fir,1);
    231. 	}
    232. 	init_dfs(rt,0,1);
    233. 	dfs2(rt,rt);
    234. 	build(1,1,n);
    235. 	m=read();
    236. 	while(m--)
    237. 	{
    238. 		op=read();
    239. 		if(op==2)
    240. 		{
    241. 			x=read();y=read();z=read();
    242. 			tree_add(x,y,z);
    243. 			continue;
    244. 		}
    245. 		else if(op==4)
    246. 		{
    247. 			x=read();y=read();
    248. 			printf("%lld\n",tree_sum(x,y));
    249. 			continue;
    250. 		}
    251. 		else if(op==3)
    252. 		{
    253. 			
    254. 			x=read();z=read();
    255. 			trson_add(x,z);
    256. 			continue;
    257. 		}
    258. 		else if(op==5)
    259. 		{
    260. 			x=read();
    261. 			printf("%lld\n",trson_sum(x));
    262. 			continue;
    263. 		}
    264. 		else if(op==1)
    265. 		{
    266. 			x=read();
    267. 			rt=x;
    268. 		}
    269. 	}
    270. 	return 0;
    271. }

     Max Flow P

     大意:
    操作1：路径总体权值+1

    操作2：查询路径最大值

    思路：

    很显然也是板子，线段树维护区间最大值即可

    1. #include
    2. using namespace std;
    3. #define ll int
    4. #define endl '\n'
    5. const ll N=5e4+10;
    6. struct ty{
    7. 	ll t,l,next;
    8. }edge[N<<1];
    9. ll cn=0;
    10. ll n,k;
    11. ll aa,b,c,rt;
    12. ll head[N];
    13. void add_edge(ll a,ll b,ll c)
    14. {
    15. 	edge[++cn].t=b;
    16. 	edge[cn].l=c;
    17. 	edge[cn].next=head[a];
    18. 	head[a]=cn;
    19. }
    20. struct tree
    21. {
    22. 	ll l,r;
    23. 	ll val;
    24. 	ll add;//lazy
    25. 	ll siz;
    26. }tr[N<<2];
    27. ll dep[N];//深度
    28. ll fa[N],son[N];
    29. ll siz[N];
    30. ll mas[N],a[N];//初始序列，处理后的序列
    31. ll cnt=0;//dfs序的时间戳
    32. ll top[N];//所在链的顶端
    33. ll idx[N];
    34. void init_dfs(ll id,ll p,ll depth)
    35. {
    36.     dep[id]=depth;
    37.     fa[id]=p;
    38. 	siz[id]=1;
    39. 	ll son_val=0;
    40. 	for(int i=head[id];i!=-1;i=edge[i].next)
    41. 	{
    42. 		ll y=edge[i].t;
    43. 		if(y==p) continue;
    44. 		init_dfs(y,id,depth+1);
    45. 		siz[id]+=siz[y];
    46. 		if(siz[y]>son_val)
    47. 		{
    48. 			son_val=siz[y];
    49. 			son[id]=y;
    50. 		}
    51. 	}		
    52. } 
    53. void dfs2(ll id,ll p)
    54. {//更新链上的情况 
    55. 	idx[id]=++cnt;
    56. 	a[cnt]=mas[id];
    57. 	top[id]=p;
    58. 	if(!son[id]) return;
    59. 	dfs2(son[id],p);
    60. 	for(int i=head[id];i!=-1;i=edge[i].next)
    61. 	{
    62. 		ll y=edge[i].t;
    63. 		//if(y==p||y==son[id]) continue;
    64. 		if(!idx[y]) dfs2(y,y);//新的链 
    65. 	}
    66. }
    67. void push_up(ll p)
    68. {
    69. 	tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
    70. }
    71. void build(ll p,ll l,ll r)
    72. {
    73. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    74. 	if(l==r)
    75. 	{
    76. 		tr[p].val=a[l];
    77. 		return;
    78. 	}
    79. 	ll mid=l+r>>1;
    80. 	build(p<<1,l,mid);
    81. 	build(p<<1|1,mid+1,r);
    82. }
    83. void push_down(ll p)
    84. {
    85. 	if(tr[p].add==0) return;
    86. 	tr[p<<1].val+=tr[p].add;
    87. 	tr[p<<1|1].val+=tr[p].add;
    88. 	tr[p<<1].add+=tr[p].add;
    89. 	tr[p<<1|1].add+=tr[p].add;
    90. 	tr[p].add=0;
    91. }
    92. void add(ll p,ll l,ll r,ll val)
    93. {
    94. 	if(tr[p].l>=l&&tr[p].r<=r)
    95. 	{
    96. 		tr[p].val+=val;
    97. 		tr[p].add+=val;
    98. 		return;
    99. 	}
    100. 	push_down(p);
    101. 	ll mid=tr[p].l+tr[p].r>>1;
    102. 	if(l<=mid) add(p<<1,l,r,val);
    103. 	if(r>mid) add(p<<1|1,l,r,val);
    104. 	push_up(p);
    105. }
    106. ll sum(ll p,ll l,ll r)
    107. {
    108. 	ll ans=0;
    109. 	if(tr[p].l>=l&&tr[p].r<=r)
    110. 	{
    111. 		return tr[p].val;
    112. 	}
    113. 	push_down(p);
    114. 	ll mid=tr[p].l+tr[p].r>>1;
    115. 	if(l<=mid) ans=max(ans,sum(p<<1,l,r));
    116. 	if(r>mid) ans=max(ans,sum(p<<1|1,l,r));
    117. 	return ans;
    118. }
    119. ll tree_sum(ll x,ll y)
    120. {
    121. 	ll ans=0;
    122. 	while(top[x]!=top[y])
    123. 	{
    124. 		if(dep[top[x]]swap(x,y);
    125. 		ans=max(ans,sum(1,idx[top[x]],idx[x]));
    126. 		x=fa[top[x]];
    127. 	}
    128. 	if(dep[x]swap(x,y);
    129. 	ans=max(ans,sum(1,idx[x],idx[y]));
    130. 	return ans;
    131. }
    132. ll tree_add(ll x,ll y,ll val)
    133. {
    134. 	while(top[x]!=top[y])
    135. 	{
    136. 		if(dep[top[x]]swap(x,y);
    137. 		add(1,idx[top[x]],idx[x],val);
    138. 		x=fa[top[x]];
    139. 	}
    140. 	if(dep[x]>dep[y]) swap(x,y);
    141. 	add(1,idx[x],idx[y],val);
    142. }
    143. void trson_add(ll x,ll val)
    144. {
    145. 	add(1,idx[x],idx[x]+siz[x]-1,val);
    146. }
    147. ll trson_sum(ll x)
    148. {
    149. 	return sum(1,idx[x],idx[x]+siz[x]-1);
    150. }
    151. void solve()
    152. {
    153. 	cin>>n>>k;
    154. 	for(int i=1;i
    155. 	{
    156. 		cin>>aa>>b;
    157. 		add_edge(aa,b,1);
    158. 		add_edge(b,aa,1);
    159. 	}
    160. 	init_dfs(rt,0,1);
    161. 	dfs2(rt,rt);
    162. 	build(1,1,n);
    163. 	while(k--)
    164. 	{
    165. 		cin>>aa>>b;
    166. 		tree_add(aa,b,1);
    167. 	}
    168. 	cout<<sum(1,1,n);
    169. }
    170. int main()
    171. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    172. 	memset(head,-1,sizeof head);
    173. 	rt=1;
    174. 	solve();
    175. 	return 0;
    176. }

    Grass Planting G

    边权下放点权

     大意：

    路径上边权+1，查询两点之间的边权。

    一个很明显的思路是边权下放点权，详见我的另一篇博客

    Cow Land G

    大意：

    单点修改，路径查询

    思路：

    水

    1. #include
    2. using namespace std;
    3. #define ll int
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty{
    7. 	ll t,l,next;
    8. }edge[N<<1];
    9. ll cn=0;
    10. ll head[N];
    11. ll n,q,rt;
    12. ll aa,b,op;
    13. void add_edge(ll a,ll b,ll c)
    14. {
    15. 	edge[++cn].l=c;
    16. 	edge[cn].t=b;
    17. 	edge[cn].next=head[a];
    18. 	head[a]=cn;
    19. }
    20. struct tree{
    21. 	ll l,r;
    22. 	ll val;
    23. 	ll add;
    24. 	ll siz;
    25. }tr[N<<2];
    26. ll dep[N];
    27. ll siz[N],son[N],fa[N];
    28. ll a[N],mas[N];
    29. ll cnt=0;//dfn时间戳
    30. ll idx[N]; 
    31. ll top[N];
    32. void init_dfs(ll id,ll p,ll depth)
    33. {
    34. 	dep[id]=depth;
    35. 	fa[id]=p;
    36. 	siz[id]=1;
    37. 	ll son_size=0;
    38. 	for(int i=head[id];i!=-1;i=edge[i].next)
    39. 	{
    40. 		ll y=edge[i].t;
    41. 		if(y==p) continue;
    42. 		init_dfs(y,id,depth+1);
    43. 		siz[id]+=siz[y];
    44. 		if(siz[y]>son_size)
    45. 		{
    46. 			son[id]=y;
    47. 			son_size=siz[y];
    48. 		}
    49. 	}
    50. }
    51. void dfs2(ll id,ll p)
    52. {
    53. 	idx[id]=++cnt;
    54. 	a[cnt]=mas[id];
    55. 	top[id]=p;
    56. 	if(!son[id]) return;
    57. 	dfs2(son[id],p);
    58. 	for(int i=head[id];i!=-1;i=edge[i].next)
    59. 	{
    60. 		ll y=edge[i].t;
    61. 		if(!idx[y]) dfs2(y,y);
    62. 	}
    63. }
    64. void push_up(ll p)
    65. {
    66. 	tr[p].val=(tr[p<<1].val^tr[p<<1|1].val);
    67. }
    68. void build(ll p,ll l,ll r)
    69. {
    70. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    71. 	if(l==r)
    72. 	{
    73. 		tr[p].val=a[l];
    74. 		return;
    75. 	}
    76. 	ll mid=l+r>>1;
    77. 	build(p<<1,l,mid);
    78. 	build(p<<1|1,mid+1,r);
    79. 	push_up(p);
    80. }
    81. void add(ll p,ll l,ll r,ll val)
    82. {
    83. 	if(tr[p].l==tr[p].r)
    84. 	{
    85. 		tr[p].val=val;
    86. 		return;
    87. 	}
    88. 	ll mid=tr[p].l+tr[p].r>>1;
    89. 	if(l<=mid) add(p<<1,l,r,val);
    90. 	else add(p<<1|1,l,r,val);
    91. 	push_up(p);
    92. }
    93. ll sum(ll p,ll l,ll r)
    94. {
    95. 	if(tr[p].l>=l&&tr[p].r<=r)
    96. 	{
    97. 		return tr[p].val;
    98. 	}
    99. 	ll mid=tr[p].l+tr[p].r>>1;
    100. 	ll ans=0;
    101. 	if(l<=mid) ans^=sum(p<<1,l,r);
    102. 	if(r>mid) ans^=sum(p<<1|1,l,r);
    103. 	return ans;
    104. }
    105. void tree_add(ll x,ll y,ll val)
    106. {
    107. 	while(top[x]!=top[y])
    108. 	{
    109. 		if(dep[top[x]]swap(x,y);
    110. 		add(1,idx[top[x]],idx[x],val);
    111. 		x=fa[top[x]];
    112. 	}
    113. 	if(dep[x]>dep[y]) swap(x,y);
    114. 	add(1,idx[x],idx[y],val);
    115. }
    116. ll tree_sum(ll x,ll y)
    117. {
    118. 	ll ans=0;
    119. 	while(top[x]!=top[y])
    120. 	{
    121. 		if(dep[top[x]]swap(x,y);
    122. 		ans^=sum(1,idx[top[x]],idx[x]);
    123. 		x=fa[top[x]];
    124. 	}
    125. 	if(dep[x]>dep[y]) swap(x,y);
    126. 	ans^=sum(1,idx[x],idx[y]);
    127. 	return ans;
    128. }
    129. int main()
    130. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    131. 	memset(head,-1,sizeof head);
    132. 	rt=1;
    133. 	cin>>n>>q;
    134. 	for(int i=1;i<=n;++i) cin>>mas[i];
    135. 	for(int i=1;i
    136. 	{
    137. 		cin>>aa>>b;
    138. 		add_edge(aa,b,1);
    139. 		add_edge(b,aa,1);
    140. 	}
    141. 	init_dfs(rt,0,1);
    142. 	dfs2(rt,rt);
    143. 	build(1,1,n);
    144. 	while(q--)
    145. 	{
    146. 		cin>>op>>aa>>b;
    147. 		if(op==1)
    148. 		{
    149. 			tree_add(aa,aa,b);
    150. 		}
    151. 		else cout<<tree_sum(aa,b)<
    152. 	}
    153. 	return 0; 
    154. }

    [HEOI2016/TJOI2016]树

    大意：

     思路：

    要求祖先最近，也就是求该点到根的路径上深度最深的被标记过的点。

    那么线段树记录被标记过的点的dfn序，然后维护区间最大值即可。注意处置记为-1

    1. #include
    2. using namespace std;
    3. #define ll int
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty{
    7. 	ll t,l,next;
    8. }edge[N<<1];
    9. ll cn=0;
    10. ll head[N];
    11. ll n,q,rt;
    12. ll aa,b;
    13. ll sd[N];
    14. char op;
    15. void add_edge(ll a,ll b,ll c)
    16. {
    17. 	edge[++cn].l=c;
    18. 	edge[cn].t=b;
    19. 	edge[cn].next=head[a];
    20. 	head[a]=cn;
    21. }
    22. struct tree{
    23. 	ll l,r;
    24. 	ll val;
    25. 	ll add;
    26. 	ll siz;
    27. }tr[N<<2];
    28. ll dep[N];
    29. ll siz[N],son[N],fa[N];
    30. ll a[N],mas[N];
    31. ll cnt=0;//dfn时间戳
    32. ll idx[N]; 
    33. ll top[N];
    34. void init_dfs(ll id,ll p,ll depth)
    35. {
    36. 	dep[id]=depth;
    37. 	fa[id]=p;
    38. 	siz[id]=1;
    39. 	ll son_size=0;
    40. 	for(int i=head[id];i!=-1;i=edge[i].next)
    41. 	{
    42. 		ll y=edge[i].t;
    43. 		if(y==p) continue;
    44. 		init_dfs(y,id,depth+1);
    45. 		siz[id]+=siz[y];
    46. 		if(siz[y]>son_size)
    47. 		{
    48. 			son[id]=y;
    49. 			son_size=siz[y];
    50. 		}
    51. 	}
    52. }
    53. void dfs2(ll id,ll p)
    54. {
    55. 	idx[id]=++cnt;
    56. 	sd[cnt]=id;
    57. 	a[cnt]=mas[id];
    58. 	top[id]=p;
    59. 	if(!son[id]) return;
    60. 	dfs2(son[id],p);
    61. 	for(int i=head[id];i!=-1;i=edge[i].next)
    62. 	{
    63. 		ll y=edge[i].t;
    64. 		if(!idx[y]) dfs2(y,y);
    65. 	}
    66. }
    67. void push_up(ll p)
    68. {
    69. 	tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
    70. }
    71. void build(ll p,ll l,ll r)
    72. {
    73. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    74. 	if(l==r)
    75. 	{
    76. 		tr[p].val=-1;
    77. 		return;
    78. 	}
    79. 	ll mid=l+r>>1;
    80. 	build(p<<1,l,mid);
    81. 	build(p<<1|1,mid+1,r);
    82. 	push_up(p);
    83. }
    84. void add(ll p,ll l,ll r,ll val)
    85. {
    86. 	if(tr[p].l==tr[p].r)
    87. 	{
    88. 		if(val) tr[p].val=tr[p].l;
    89. 		return;
    90. 	}
    91. 	ll mid=tr[p].l+tr[p].r>>1;
    92. 	if(l<=mid) add(p<<1,l,r,val);
    93. 	else add(p<<1|1,l,r,val);
    94. 	push_up(p);
    95. }
    96. ll sum(ll p,ll l,ll r)
    97. {
    98. 	if(tr[p].l>=l&&tr[p].r<=r)
    99. 	{
    100. 		return tr[p].val;
    101. 	}
    102. 	ll mid=tr[p].l+tr[p].r>>1;
    103. 	ll ans=-1;
    104. 	if(l<=mid) ans=max(ans,sum(p<<1,l,r));
    105. 	if(r>mid) ans=max(ans,sum(p<<1|1,l,r));
    106. 	return ans;
    107. }
    108. void tree_add(ll x,ll y,ll val)
    109. {
    110. 	while(top[x]!=top[y])
    111. 	{
    112. 		if(dep[top[x]]swap(x,y);
    113. 		add(1,idx[top[x]],idx[x],val);
    114. 		x=fa[top[x]];
    115. 	}
    116. 	if(dep[x]>dep[y]) swap(x,y);
    117. 	add(1,idx[x],idx[y],val);
    118. }
    119. ll tree_sum(ll x,ll y)
    120. {
    121. 	ll ans=-1;
    122. 	while(top[x]!=top[y])
    123. 	{
    124. 		if(dep[top[x]]swap(x,y);
    125. 		ans=sum(1,idx[top[x]],idx[x]);
    126. 		if(ans!=-1) return sd[ans];
    127. 		x=fa[top[x]];
    128. 	}
    129. 	if(dep[x]>dep[y]) swap(x,y);
    130. 	ans=sum(1,idx[x],idx[y]);
    131. 	return sd[ans];
    132. }
    133. int main()
    134. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    135. 	memset(head,-1,sizeof head);
    136. 	rt=1;
    137. 	cin>>n>>q;
    138. 	//for(int i=1;i<=n;++i) cin>>mas[i];
    139. 	for(int i=1;i
    140. 	{
    141. 		cin>>aa>>b;
    142. 		add_edge(aa,b,1);
    143. 		add_edge(b,aa,1);
    144. 	}
    145. 	init_dfs(rt,0,1);
    146. 	dfs2(rt,rt);
    147. 	build(1,1,n);
    148. 	add(1,1,1,1);
    149. 	while(q--)
    150. 	{
    151. 		cin>>op>>aa;
    152. 		if(op=='C')
    153. 		{
    154. 			add(1,idx[aa],idx[aa]+1,1);
    155. 		//	tree_add(aa,aa,1);
    156. 		}
    157. 		else cout<<tree_sum(aa,1)<
    158. 	}
    159. 	return 0; 
    160. }

    月下毛景树

    区间覆盖

    大意：

    操作比较多，有三个修改操作，对于第二/三个操作，我们记录add2，add1（别问我为什么是反的，写的时候脑子丢了吧...）.pushdown时很明显先处理add2，因为它代表区间替换，那么之前有没有加的操作并不重要，当然得把add1儿子的add1清零。然后再加上边权与点权的转换就可以了。代码还是有点长的，写起来很酸爽。

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty
    7. {
    8.     ll t,l,next;	
    9. }edge[N<<1];
    10. struct tree
    11. {
    12. 	ll l,r;
    13. 	ll val;
    14. 	ll add1,add2=-1;//加，替换 
    15. 	ll siz;
    16. }tr[N<<2];
    17. ll cn=0;
    18. ll head[N];
    19. void add_edge(ll a,ll b,ll c)
    20. {
    21. 	edge[++cn].t=b;
    22. 	edge[cn].l=c;
    23. 	edge[cn].next=head[a];
    24. 	head[a]=cn;
    25. }
    26. ll siz[N],fa[N],son[N],dep[N],idx[N],a[N],mas[N],top[N]; 
    27. ll n,m,cnt,rt,fir,sec,thi,x,y,z;
    28. pair church[N];
    29. string op;
    30. void init_dfs(ll id,ll p,ll depth)
    31. {
    32. 	siz[id]=1;
    33. 	dep[id]=depth;
    34. 	fa[id]=p;
    35. 	ll son_val=0;
    36. 	for(int i=head[id];i!=-1;i=edge[i].next)
    37. 	{
    38. 		ll y=edge[i].t;
    39. 		if(y==p) continue;
    40. 		mas[y]=edge[i].l;
    41. 		init_dfs(y,id,depth+1);
    42. 		siz[id]+=siz[y];
    43. 		if(siz[y]>son_val)
    44. 		{
    45. 			son_val=siz[y];
    46. 			son[id]=y;
    47. 		}	
    48. 	}
    49. }
    50. void dfs2(ll id,ll p)
    51. {
    52. 	top[id]=p;
    53. 	idx[id]=++cnt;
    54. 	a[cnt]=mas[id];
    55. 	if(!son[id]) return;
    56. 	dfs2(son[id],p);
    57. 	for(int i=head[id];i!=-1;i=edge[i].next)
    58. 	{
    59. 		ll y=edge[i].t;
    60. 		if(!idx[y]) dfs2(y,y);
    61. 	}
    62. }
    63. void push_up(ll p)
    64. {
    65. 	tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
    66. }
    67. void push_down(ll p)
    68. {
    69. 	if(tr[p].add2>=0)
    70. 	{
    71. 		tr[p<<1].add1=tr[p<<1|1].add1=0;
    72. 		tr[p<<1].val=tr[p<<1|1].val=tr[p].add2;
    73. 		tr[p<<1].add2=tr[p<<1|1].add2=tr[p].add2;
    74. 		tr[p].add2=-1;
    75. 	}
    76. 	if(tr[p].add1)
    77. 	{
    78. 		tr[p<<1].add1+=tr[p].add1;
    79. 		tr[p<<1|1].add1+=tr[p].add1;
    80. 		tr[p<<1].val+=tr[p].add1;
    81. 		tr[p<<1|1].val+=tr[p].add1;
    82. 		tr[p].add1=0;
    83. 	}
    84. }
    85. void build(ll p,ll l,ll r)
    86. {
    87. 	tr[p].l=l;tr[p].r=r;
    88. 	tr[p].siz=r-l+1;
    89. 	if(l==r)
    90. 	{
    91. 		tr[p].val=a[l];
    92. 		tr[p].add1=0;tr[p].add2=-1;
    93. 		return;
    94. 	}
    95. 	ll mid=r+l>>1;
    96. 	build(p<<1,l,mid);
    97. 	build(p<<1|1,mid+1,r);
    98. 	push_up(p);
    99. }
    100. void ti_huan(ll p,ll l,ll r,ll val)//cover 
    101. {
    102. 	if(tr[p].l>=l&&tr[p].r<=r)
    103. 	{
    104. 		tr[p].val=val;
    105. 		tr[p].add1=0;tr[p].add2=val;
    106. 		return;
    107. 	}
    108. 	push_down(p);
    109. 	ll mid=tr[p].l+tr[p].r>>1;
    110. 	if(l<=mid) ti_huan(p<<1,l,r,val);
    111. 	if(r>mid) ti_huan(p<<1|1,l,r,val);
    112. 	push_up(p);
    113. }
    114. void add(ll p,ll l,ll r,ll val)
    115. {
    116. 	if(tr[p].l>=l&&tr[p].r<=r)
    117. 	{
    118. 		tr[p].val+=val;
    119. 		tr[p].add1+=val;
    120. 		return;
    121. 	}
    122. 	push_down(p);
    123. 	ll mid=tr[p].l+tr[p].r>>1;
    124. 	if(l<=mid) add(p<<1,l,r,val);
    125. 	if(r>mid) add(p<<1|1,l,r,val);
    126. 	push_up(p);
    127. }
    128. ll sum(ll p,ll l,ll r)
    129. {
    130. 	if(tr[p].l>=l&&tr[p].r<=r)
    131. 	{
    132. 		return tr[p].val;
    133. 	}
    134. 	ll ans=0;
    135. 	push_down(p);
    136. 	ll mid=tr[p].l+tr[p].r>>1;
    137. 	if(l<=mid) ans=max(ans,sum(p<<1,l,r));
    138. 	if(r>mid) ans=max(ans,sum(p<<1|1,l,r));
    139. 	//cout<<"SUM "<
    140. 	return ans;
    141. }
    142. void change(ll p,ll l,ll val)
    143. {
    144. 	if(tr[p].l==tr[p].r)
    145. 	{
    146. 		tr[p].add1=0;
    147. 		tr[p].add2=val;
    148. 		tr[p].val=val;
    149. 		return;
    150. 	}
    151. 	push_down(p);
    152. 	ll mid=tr[p].l+tr[p].r>>1;
    153. 	if(l<=mid) change(p<<1,l,val);
    154. 	else change(p<<1|1,l,val);
    155. 	push_up(p);
    156. }
    157. void tree_cover(ll x,ll y,ll val)
    158. {
    159. 	while(top[x]!=top[y])
    160. 	{
    161. 		if(dep[top[x]]swap(x,y);
    162. 		ti_huan(1,idx[top[x]],idx[x],val);
    163. 		x=fa[top[x]];
    164. 	}
    165. 	if(dep[x]>dep[y]) swap(x,y);
    166. 	ti_huan(1,idx[x]+1,idx[y],val);
    167. }
    168. void tree_add(ll x,ll y,ll val)
    169. {
    170. 	while(top[x]!=top[y])
    171. 	{
    172. 		if(dep[top[x]]swap(x,y);
    173. 		add(1,idx[top[x]],idx[x],val);
    174. 		x=fa[top[x]];
    175. 	}
    176. 	if(dep[x]>dep[y]) swap(x,y);
    177. 	add(1,idx[x]+1,idx[y],val);
    178. }
    179. ll tree_sum(ll x,ll y)
    180. {
    181. 	ll ans=0;
    182. 	while(top[x]!=top[y])
    183. 	{
    184. 		if(dep[top[x]]swap(x,y);
    185. 		ans=max(ans,sum(1,idx[top[x]],idx[x]));
    186. 		x=fa[top[x]];
    187. 	}
    188. 	if(dep[x]>dep[y]) swap(x,y);
    189. 	ans=max(ans,sum(1,idx[x]+1,idx[y]));
    190. 	return ans;
    191. }
    192. int main()
    193. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    194. 	memset(head,-1,sizeof head);
    195. 	cin>>n;
    196. 	for(int i=1;i
    197. 	{
    198. 		cin>>fir>>sec>>thi;
    199. 		add_edge(fir,sec,thi);
    200. 		add_edge(sec,fir,thi);
    201. 		church[i]=make_pair(fir,sec);
    202. 	}
    203. 	rt=1;
    204. 	init_dfs(rt,0,1);
    205. 	dfs2(rt,rt);
    206. 	build(1,1,n);
    207. //	for(int i=1;i<=n;++i) cout<
    208. 	while(cin>>op)
    209. 	{
    210. 		if(op[0]=='S') break;
    211. 		if(op=="Max")
    212. 		{
    213. 			cin>>x>>y;
    214. 			cout<<tree_sum(x,y)<
    215. 			continue;
    216. 		}
    217. 		if(op=="Cover")
    218. 		{
    219. 			cin>>x>>y>>z;
    220. 			tree_cover(x,y,z);
    221. 			continue;
    222. 		}
    223. 		if(op=="Add")
    224. 		{
    225. 			cin>>x>>y>>z;
    226. 			tree_add(x,y,z);
    227. 			continue;
    228. 		}
    229. 		if(op=="Change")
    230. 		{
    231. 			cin>>x>>y;
    232. 			ll sd;
    233. 			if(dep[church[x].first]>dep[church[x].second]) sd=church[x].first;
    234. 			else sd=church[x].second;
    235. 			change(1,idx[sd],y);
    236. 		}
    237. 	}
    238. 	return 0;
    239. }

    树的统计

    大意：

    思路：

    基操，只是维护了两个值而已。

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=2e5+10;
    6. struct ty{
    7. 	ll t,l,next;
    8. }edge[N<<1];
    9. ll head[N];
    10. ll cn=0;
    11. void add_edge(ll a,ll b,ll c)
    12. {
    13. 	edge[++cn].t=b;
    14. 	edge[cn].l=c;
    15. 	edge[cn].next=head[a];
    16. 	head[a]=cn;
    17. }
    18. struct tree
    19. {
    20. 	ll l,r;
    21. 	ll val;
    22. 	ll maxn;
    23. 	ll add;
    24. 	ll siz;
    25. }tr[N<<2];
    26. ll siz[N],fa[N],idx[N],a[N],mas[N],top[N],son[N],dep[N];
    27. ll n,m,rt,fir,sec,x,y,z,cnt;
    28. string op;
    29. void init_dfs(ll id,ll p,ll depth)
    30. {
    31. 	fa[id]=p;
    32. 	dep[id]=depth;
    33. 	siz[id]=1;
    34. 	ll son_val=0;
    35. 	for(int i=head[id];i!=-1;i=edge[i].next)
    36. 	{
    37. 		ll y=edge[i].t;
    38. 		if(y==p) continue;
    39. 		init_dfs(y,id,depth+1);
    40. 		siz[id]+=siz[y];
    41. 		if(siz[y]>=son_val)
    42. 		{
    43. 			son_val=siz[y];
    44. 			son[id]=y;			
    45. 		}
    46. 	}
    47. }
    48. void dfs2(ll id,ll p)
    49. {
    50. 	top[id]=p;
    51. 	idx[id]=++cnt;
    52. 	a[cnt]=mas[id];
    53. 	if(!son[id]) return;
    54. 	dfs2(son[id],p);
    55. 	for(int i=head[id];i!=-1;i=edge[i].next)
    56. 	{
    57. 		ll y=edge[i].t;
    58. 		if(!idx[y]) dfs2(y,y);
    59. 	}
    60. }
    61. void push_up(ll p)
    62. {
    63. 	tr[p].maxn=max(tr[p<<1].maxn,tr[p<<1|1].maxn);
    64. 	tr[p].val=tr[p<<1].val+tr[p<<1|1].val;
    65. }
    66. void build(ll p,ll l,ll r)
    67. {
    68. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    69. 	if(l==r)
    70. 	{
    71. 		tr[p].maxn=tr[p].val=a[l];
    72. 		return;
    73. 	}
    74. 	ll mid=l+r>>1;
    75. 	build(p<<1,l,mid);
    76. 	build(p<<1|1,mid+1,r);
    77. 	push_up(p);
    78. }
    79. void change(ll p,ll l,ll val)
    80. {
    81. 	if(tr[p].l==tr[p].r)
    82. 	{
    83. 		tr[p].val=tr[p].maxn=val;
    84. 		return;
    85. 	}
    86. 	ll mid=tr[p].l+tr[p].r>>1;
    87. 	if(l<=mid) change(p<<1,l,val);
    88. 	else change(p<<1|1,l,val);
    89. 	push_up(p);
    90. }
    91. ll sum(ll p,ll l,ll r)
    92. {
    93. 	if(tr[p].l>=l&&tr[p].r<=r)
    94. 	{
    95. 		return tr[p].val;
    96. 	}
    97. 	ll mid=tr[p].l+tr[p].r>>1;
    98. 	ll ans=0;
    99. 	if(l<=mid) ans+=sum(p<<1,l,r);
    100. 	if(r>mid) ans+=sum(p<<1|1,l,r);
    101. 	return ans; 
    102. }
    103. ll maxn(ll p,ll l,ll r)
    104. {
    105. 	if(tr[p].l>=l&&tr[p].r<=r)
    106. 	{
    107. 		return tr[p].maxn;
    108. 	}
    109. 	ll mid=tr[p].l+tr[p].r>>1;
    110. 	ll ans=-1e15;
    111. 	if(l<=mid) ans=max(ans,maxn(p<<1,l,r));
    112. 	if(r>mid) ans=max(ans,maxn(p<<1|1,l,r));
    113. 	return ans;
    114. }
    115. ll tree_sum(ll x,ll y)
    116. {
    117. 	ll ans=0;
    118. 	while(top[x]!=top[y])
    119. 	{
    120. 		if(dep[top[x]]swap(x,y);
    121. 		ans+=sum(1,idx[top[x]],idx[x]);
    122. 		x=fa[top[x]];
    123. 	}
    124. 	if(dep[x]>dep[y]) swap(x,y);
    125. 	ans+=sum(1,idx[x],idx[y]);
    126. 	return ans;
    127. }
    128. ll tree_maxn(ll x,ll y)
    129. {
    130. 	ll ans=-1e15;
    131. 	while(top[x]!=top[y])
    132. 	{
    133. 		if(dep[top[x]]swap(x,y);
    134. 		ans=max(ans,maxn(1,idx[top[x]],idx[x]));
    135. 		x=fa[top[x]];
    136. 	}
    137. 	if(dep[x]>dep[y]) swap(x,y);
    138. 	ans=max(ans,maxn(1,idx[x],idx[y]));
    139. 	return ans;
    140. }
    141. int main()
    142. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    143. 	memset(head,-1,sizeof head);
    144. 	cin>>n;
    145. 	for(int i=1;i
    146. 	{
    147. 		cin>>fir>>sec;
    148. 		add_edge(fir,sec,1);
    149. 		add_edge(sec,fir,1);
    150. 	}
    151. 	for(int i=1;i<=n;++i) cin>>mas[i];
    152. 	cin>>m;
    153. 	rt=1;
    154. 	init_dfs(rt,0,1);
    155. 	dfs2(rt,rt);
    156. 	build(1,1,n);
    157. 	for(int i=1;i<=m;++i)
    158. 	{
    159. 		cin>>op;
    160. 		cin>>x>>y;
    161. 		if(op[0]=='C')
    162. 		{
    163. 			change(1,idx[x],y);
    164. 			continue;
    165. 		}
    166. 		else if(op[1]=='M')
    167. 		{
    168. 			cout<<tree_maxn(x,y)<
    169. 		}
    170. 		else cout<<tree_sum(x,y)<
    171. 	}
    172. 	return 0;
    173. }

     [SHOI2012]魔法树

    大意：

    区间加，子树查询

    思路：

    还是板子

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=2e5+10;
    6. struct ty
    7. {
    8. 	ll t,l,next;
    9. }edge[N<<1];
    10. ll head[N];
    11. ll cn=0;
    12. void add_edge(ll a,ll b,ll c)
    13. {
    14. 	edge[++cn].t=b;
    15. 	edge[cn].next=head[a];
    16. 	edge[cn].l=c;
    17. 	head[a]=cn;
    18. }
    19. struct tree
    20. {
    21. 	ll l,r;
    22. 	ll val;
    23. 	ll add;
    24. 	ll siz;
    25. }tr[N<<2];
    26. ll son[N],fa[N],siz[N],top[N],dep[N],idx[N],a[N],mas[N];
    27. ll cnt=0,n,m,rt,fir,sec,x,y,z;
    28. char op;
    29. void init_dfs(ll id,ll p,ll depth)
    30. {
    31. 	dep[id]=depth;
    32. 	fa[id]=p;
    33. 	siz[id]=1;
    34. 	ll son_val=0;
    35. 	for(int i=head[id];i!=-1;i=edge[i].next)
    36. 	{
    37. 		ll y=edge[i].t;
    38. 		if(y==p) continue;
    39. 		init_dfs(y,id,depth+1);
    40. 		siz[id]+=siz[y];
    41. 		if(siz[y]>son_val)
    42. 		{
    43. 			son_val=siz[y];
    44. 			son[id]=y;
    45. 		}
    46. 	}
    47. }
    48. void dfs2(ll id,ll p)
    49. {
    50. 	top[id]=p;
    51. 	idx[id]=++cnt;
    52. 	a[cnt]=mas[id];
    53. 	if(!son[id]) return;
    54. 	dfs2(son[id],p);
    55. 	for(int i=head[id];i!=-1;i=edge[i].next)
    56. 	{
    57. 		ll y=edge[i].t;
    58. 		if(!idx[y]) dfs2(y,y);
    59. 	}
    60. }
    61. void push_up(ll p)
    62. {
    63. 	tr[p].val=tr[p<<1].val+tr[p<<1|1].val;
    64. }
    65. void push_down(ll p)
    66. {
    67. 	if(tr[p].add==0) return;
    68. 	tr[p<<1].val+=tr[p<<1].siz*tr[p].add;
    69. 	tr[p<<1|1].val+=tr[p<<1|1].siz*tr[p].add;
    70. 	tr[p<<1].add+=tr[p].add;
    71. 	tr[p<<1|1].add+=tr[p].add;
    72. 	tr[p].add=0;
    73. }
    74. void build(ll p,ll l,ll r)
    75. {
    76. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    77. 	if(l==r)
    78. 	{
    79. 		tr[p].val=a[l];
    80. 		return;
    81. 	}
    82. 	ll mid=l+r>>1;
    83. 	build(p<<1,l,mid);
    84. 	build(p<<1|1,mid+1,r);
    85. 	push_up(p);
    86. }
    87. void add(ll p,ll l,ll r,ll val)
    88. {
    89. 	if(tr[p].l>=l&&tr[p].r<=r)
    90. 	{
    91. 		tr[p].val+=tr[p].siz*val;
    92. 		tr[p].add+=val;
    93. 		return;
    94. 	}
    95. 	push_down(p);
    96. 	ll mid=tr[p].l+tr[p].r>>1;
    97. 	if(l<=mid) add(p<<1,l,r,val);
    98. 	if(r>mid) add(p<<1|1,l,r,val);
    99. 	push_up(p);
    100. }
    101. ll sum(ll p,ll l,ll r)
    102. {
    103. 	if(tr[p].l>=l&&tr[p].r<=r)
    104. 	{
    105. 		return tr[p].val;
    106. 	}
    107. 	push_down(p);
    108. 	ll mid=tr[p].l+tr[p].r>>1;
    109. 	ll ans=0;
    110. 	if(l<=mid) ans+=sum(p<<1,l,r);
    111. 	if(r>mid) ans+=sum(p<<1|1,l,r);
    112. 	return ans;
    113. }
    114. void tree_add(ll x,ll y,ll val)
    115. {
    116. 	while(top[x]!=top[y])
    117. 	{
    118. 		if(dep[top[x]]swap(x,y);
    119. 		add(1,idx[top[x]],idx[x],val);
    120. 		x=fa[top[x]];
    121. 	}
    122. 	if(dep[x]>dep[y]) swap(x,y);
    123. 	add(1,idx[x],idx[y],val);
    124. }
    125. ll tree_sum(ll x,ll y)
    126. {
    127. 	ll ans=0;
    128. 	while(top[x]!=top[y])
    129. 	{
    130. 		if(dep[top[x]]swap(x,y);
    131. 		ans+=sum(1,idx[top[x]],idx[x]);
    132. 		x=fa[top[x]]; 
    133. 	}
    134. 	if(dep[x]>dep[y]) swap(x,y);
    135. 	ans+=sum(1,idx[x],idx[y]);
    136. 	return ans;
    137. }
    138. ll trson_sum(ll x)
    139. {
    140. 	return sum(1,idx[x],idx[x]+siz[x]-1);
    141. }
    142. int main()
    143. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    144. 	memset(head,-1,sizeof head);
    145. 	cin>>n;
    146. 	for(int i=1;i
    147. 	{
    148. 		cin>>fir>>sec;
    149. 		fir++;sec++;
    150. 		add_edge(fir,sec,1);
    151. 		add_edge(sec,fir,1);
    152. 	}
    153. 	cin>>m;
    154. 	rt=1;
    155. 	init_dfs(rt,0,1);
    156. 	dfs2(rt,rt);
    157. 	build(1,1,n);
    158. 	while(m--)
    159. 	{
    160. 		cin>>op;
    161. 		if(op=='A')
    162. 		{
    163. 			cin>>x>>y>>z;
    164. 			x++;y++;
    165. 			tree_add(x,y,z);
    166. 			continue;
    167. 		}
    168. 		cin>>x;
    169. 		x++;
    170. 		cout<<trson_sum(x)<
    171. 	}
    172. 	return 0;
    173. }

    [NOI2015] 软件包管理器

     大意：
    install操作：查询节点到根的权值为0的个数，并区间置1

    unstall操作：查询子树权值为1的个数，并区间置0

    思路：

    区间置操作是很简单的，没什么好讲

    对于第一种操作，记录一下修改前的值，那么区间长度减去它就是答案了

    对于第二种操作，直接返回区间和就可以了

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty
    7. {
    8. 	ll t,l,next;
    9. }edge[N<<1];
    10. ll cn=0;
    11. ll head[N];
    12. void add_edge(ll a,ll b,ll c)
    13. {
    14. 	edge[++cn].t=b;
    15. 	edge[cn].l=c;
    16. 	edge[cn].next=head[a];
    17. 	head[a]=cn;
    18. }
    19. struct tree
    20. {
    21. 	ll l,r,siz=0;
    22. 	ll add=0;
    23. 	ll val=0;
    24. }tr[N<<2];
    25. ll siz[N],dep[N],son[N],fa[N],idx[N],mas[N],a[N],top[N];
    26. ll n,m,fir,sec,cnt,x,y,z,rt;
    27. string op;
    28. void init_dfs(ll id,ll p,ll depth)
    29. {
    30. 	fa[id]=p;
    31. 	dep[id]=depth;
    32. 	siz[id]=1;
    33. 	ll son_val=0;
    34. 	for(int i=head[id];i!=-1;i=edge[i].next)
    35. 	{
    36. 		ll y=edge[i].t;
    37. 		if(y==p) continue;
    38. 		init_dfs(y,id,depth+1);
    39. 		siz[id]+=siz[y];
    40. 		if(siz[y]>son_val)
    41. 		{
    42. 			son_val=siz[y];
    43. 			son[id]=y;
    44. 		}
    45. 	}
    46. }
    47. void dfs2(ll id,ll p)
    48. {
    49. 	top[id]=p;
    50. 	idx[id]=++cnt;
    51. 	a[cnt]=mas[id];
    52. 	if(!son[id]) return;
    53. 	dfs2(son[id],p);
    54. 	for(int i=head[id];i!=-1;i=edge[i].next)
    55. 	{
    56. 		ll y=edge[i].t;
    57. 		if(!idx[y]) dfs2(y,y);
    58. 	}
    59. }
    60. void push_up(ll p)
    61. {
    62. 	tr[p].val=tr[p<<1].val+tr[p<<1|1].val;
    63. }
    64. void build(ll p,ll l,ll r)
    65. {
    66. 	tr[p].l=l;tr[p].r=r;
    67. 	tr[p].siz=r-l+1;
    68. 	if(l==r)
    69. 	{
    70. 		tr[p].val=0;
    71. 		tr[p].add=-1;
    72. 		return;
    73. 	}
    74. 	ll mid=l+r>>1;
    75. 	build(p<<1,l,mid);
    76. 	build(p<<1|1,mid+1,r);
    77. }
    78. void push_down(ll p)
    79. {
    80. 	if(tr[p].add==-1) return;
    81. 	tr[p<<1].add=tr[p<<1|1].add=tr[p].add;
    82. 	if(tr[p].add==0)
    83. 	{
    84. 		tr[p<<1].val=tr[p<<1|1].val=0;
    85. 	}
    86. 	else if(tr[p].add==1)
    87. 	{
    88. 		tr[p<<1].val=tr[p<<1].siz;
    89. 		tr[p<<1|1].val=tr[p<<1|1].siz;
    90. 	}
    91. 	tr[p].add=-1;
    92. }
    93. ll get_sum(ll p,ll l,ll r)//子树使用,途径置0 
    94. {
    95. 	if(tr[p].l>=l&&tr[p].r<=r)
    96. 	{
    97. 		ll ans=tr[p].val;
    98. 		tr[p].val=0;
    99. 		tr[p].add=0;
    100. 		return ans;
    101. 	}
    102. 	push_down(p);
    103. 	ll ans=0;
    104. 	ll mid=tr[p].l+tr[p].r>>1;
    105. 	if(l<=mid) ans+=get_sum(p<<1,l,r);
    106. 	if(r>mid) ans+=get_sum(p<<1|1,l,r);
    107. 	push_up(p);
    108. 	return ans;
    109. }
    110. ll sum(ll p,ll l,ll r)
    111. {
    112. 	if(tr[p].l>=l&&tr[p].r<=r)
    113. 	{
    114. 		ll ans=tr[p].val;
    115. 		tr[p].val=tr[p].siz;
    116. 		tr[p].add=1;
    117. 		return tr[p].siz-ans;
    118. 	}
    119. 	push_down(p);
    120. 	ll ans=0;
    121. 	ll mid=tr[p].l+tr[p].r>>1;
    122. 	if(l<=mid) ans+=sum(p<<1,l,r);
    123. 	if(r>mid) ans+=sum(p<<1|1,l,r);
    124. 	push_up(p);
    125. 	return ans;
    126. }
    127. ll trson_sum(ll x)
    128. {
    129. 	return get_sum(1,idx[x],idx[x]+siz[x]-1);
    130. }
    131. ll tree_sum(ll x,ll y)
    132. {
    133. 	ll ans=0;
    134. 	while(top[x]!=top[y])
    135. 	{
    136. 		if(dep[top[x]]swap(x,y);
    137. 		ans+=sum(1,idx[top[x]],idx[x]);
    138. 		x=fa[top[x]]; 
    139. 	}
    140. 	if(dep[x]>dep[y]) swap(x,y);
    141. 	ans+=sum(1,idx[x],idx[y]);
    142. 	return ans;
    143. }
    144. int main()
    145. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    146. 	memset(head,-1,sizeof head);
    147. 	cin>>n;
    148. 	for(int i=2;i<=n;++i)
    149. 	{
    150. 		cin>>fir;
    151. 		add_edge(fir+1,i,1);
    152. 		add_edge(i,fir+1,1);
    153. 	}
    154. 	rt=1;
    155. 	init_dfs(rt,0,1);
    156. 	dfs2(rt,rt);
    157. 	build(1,1,n);
    158. //	for(int i=1;i<=n;++i) cout<
    159. //	cout<
    160. 	cin>>m;
    161. 	while(m--)
    162. 	{
    163. 		cin>>op;
    164. 		cin>>x;
    165. 		x++;
    166. 		if(op[0]=='i')
    167. 		{
    168. 			cout<<tree_sum(x,1)<
    169. 			continue;
    170. 		}
    171. 		else cout<<trson_sum(x)<
    172. 	}
    173. }

    树上操作

    大意：

    思路：

    大同小异

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty
    7. {
    8. 	ll t,l,next;
    9. }edge[N<<1];
    10. ll cn=0;
    11. ll head[N];
    12. void add_edge(ll a,ll b,ll c)
    13. {
    14. 	edge[++cn].t=b;
    15. 	edge[cn].l=c;
    16. 	edge[cn].next=head[a];
    17. 	head[a]=cn;
    18. }
    19. struct tree
    20. {
    21. 	ll sum=0;
    22. 	ll add=0;
    23. 	ll l,r,size=0;
    24. }tr[N<<2];
    25. ll siz[N],son[N],fa[N],dep[N],mas[N],a[N],idx[N],top[N];
    26. ll n,m,rt,cnt,fir,sec,x,y,z,op;
    27. void init_dfs(ll id,ll p,ll depth)
    28. {
    29. 	dep[id]=depth;
    30. 	siz[id]=1;
    31. 	fa[id]=p;
    32. 	ll son_val=0;
    33. 	for(int i=head[id];i!=-1;i=edge[i].next)
    34. 	{
    35. 		ll y=edge[i].t;
    36. 		if(y==p) continue;
    37. 		init_dfs(y,id,depth+1);
    38. 		siz[id]+=siz[y];
    39. 		if(siz[y]>son_val)
    40. 		{
    41. 			son_val=siz[y];
    42. 			son[id]=y;
    43. 		}
    44. 	}
    45. }
    46. void dfs2(ll id,ll p)
    47. {
    48. 	idx[id]=++cnt;
    49. 	top[id]=p;
    50. 	a[cnt]=mas[id];
    51. 	if(!son[id]) return;
    52. 	dfs2(son[id],p);
    53. 	for(int i=head[id];i!=-1;i=edge[i].next)
    54. 	{
    55. 		ll y=edge[i].t;
    56. 		if(!idx[y]) dfs2(y,y);
    57. 	}
    58.  } 
    59.  void push_up(ll p)
    60.  {
    61.  	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
    62.  }
    63.  void push_down(ll p)
    64.  {
    65.  	if(tr[p].add==0) return;
    66.  	tr[p<<1].sum+=tr[p<<1].size*tr[p].add;
    67.  	tr[p<<1|1].sum+=tr[p<<1|1].size*tr[p].add;
    68.  	tr[p<<1].add+=tr[p].add;
    69.  	tr[p<<1|1].add+=tr[p].add;
    70.  	tr[p].add=0;
    71.  }
    72.  void build(ll p,ll l,ll r)
    73.  {
    74.  	tr[p].l=l;tr[p].r=r;tr[p].size=r-l+1;
    75.  	if(l==r)
    76.  	{
    77.  		tr[p].sum=a[l];
    78.  		return;
    79. 	}
    80. 	ll mid=l+r>>1;
    81. 	build(p<<1,l,mid);
    82. 	build(p<<1|1,mid+1,r);
    83. 	push_up(p);
    84.  }
    85.  void change(ll p,ll l,ll val)
    86.  {
    87.  	if(tr[p].l==tr[p].r)
    88.  	{
    89.  		tr[p].sum+=val;
    90.  		return;
    91. 	}
    92. 	push_down(p);
    93. 	ll mid=tr[p].l+tr[p].r>>1;
    94. 	if(l<=mid) change(p<<1,l,val);
    95. 	else change(p<<1|1,l,val);
    96. 	push_up(p);
    97.  }
    98.  void add(ll p,ll l,ll r,ll val)
    99.  {
    100.  	if(tr[p].l>=l&&tr[p].r<=r)
    101.  	{
    102.  		tr[p].sum+=tr[p].size*val;
    103.  		tr[p].add+=val;
    104.  		return;
    105. 	}
    106. 	push_down(p);
    107. 	ll mid=tr[p].l+tr[p].r>>1;
    108. 	if(l<=mid) add(p<<1,l,r,val);
    109. 	if(r>mid) add(p<<1|1,l,r,val);
    110. 	push_up(p);
    111.  }
    112.  ll sum(ll p,ll l,ll r)
    113.  {
    114.  	if(tr[p].l>=l&&tr[p].r<=r)
    115.  	{
    116.  		return tr[p].sum;
    117. 	}
    118. 	ll ans=0;
    119. 	push_down(p);
    120. 	ll mid=tr[p].l+tr[p].r>>1;
    121. 	if(l<=mid) ans+=sum(p<<1,l,r);
    122. 	if(r>mid) ans+=sum(p<<1|1,l,r);
    123. 	return ans;
    124.  }
    125. ll tree_sum(ll x,ll y)
    126. {
    127. 	ll ans=0;
    128. 	while(top[x]!=top[y])
    129. 	{
    130. 		if(dep[top[x]]swap(x,y);
    131. 		ans+=sum(1,idx[top[x]],idx[x]);
    132. 		x=fa[top[x]];
    133. 	}
    134. 	if(dep[x]>dep[y]) swap(x,y);
    135. 	ans+=sum(1,idx[x],idx[y]);
    136. 	return ans;
    137. }
    138. void trson_add(ll x,ll val)
    139. {
    140. 	add(1,idx[x],idx[x]+siz[x]-1,val);
    141. }
    142. int main()
    143. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    144. 	memset(head,-1,sizeof head);
    145. 	cin>>n>>m;
    146. 	for(int i=1;i<=n;++i) cin>>mas[i];
    147. 	for(int i=1;i
    148. 	{
    149. 		cin>>fir>>sec;
    150. 		add_edge(fir,sec,1);
    151. 		add_edge(sec,fir,1);
    152. 	}
    153. 	rt=1;
    154. 	init_dfs(rt,0,1);
    155. 	dfs2(rt,rt);
    156. 	build(1,1,n);
    157. 	while(m--)
    158. 	{
    159. 		cin>>op;
    160. 		if(op==1)
    161. 		{
    162. 			cin>>x>>y;
    163. 			change(1,idx[x],y);
    164. 			continue;
    165. 		}
    166. 		if(op==2)
    167. 		{
    168. 			cin>>x>>y;
    169. 			trson_add(x,y);
    170. 			continue;
    171. 		}
    172. 		if(op==3)
    173. 		{
    174. 			cin>>x;
    175. 			cout<<tree_sum(x,1)<
    176. 		}
    177. 		
    178. 	}
    179. 	return 0;
    180. }

    进阶 

    [USACO18OPEN]Disruption P

    大意：

    给定一棵树，以及一些多余的边。

    对于每一条树上的边，可以取一条多余的边来替代它，使得该边两端的点仍然联通。如果该操作可行，求出改变后的两点最短距离 .不行的话，输出-1 

    思路：

    正向思考可能比较难，因为对于每一条边都要考虑所有多余的边能否替换它。既然如此，不妨换个思路，考虑每一条边能更新什么。

    不难发现，对于一条多余的边，它的两边的点的路径与它可以构成一个环（见图）。环上的点都是可以相互到达的，所以这条多余的边就可以更新环上的所有边。如果我们在每一条边维护一下可以更新它的边的最小边权，这样的话，不就是路径更新最小值嘛。为了使用树剖，我们再记录一下每一条边对应的较深的节点，那么边就与节点建立了一对一的映射，就可以快乐树剖了。

    当然也可以不用树剖。我们发现这个过程还是有很多重复的操作，可以考虑使用并查集。

    对于所有多余的边，按边权从小到大排序，那么每一条边就尽可能更新它能更新的边，如果某一条边发现已经被更新过了，就跳过，因为它肯定是被更小的边更新的，由该边更新，结果不会更优。这个跳过的操作，用并查集维护就可以了。

    求lca时也可以用一下树剖

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty
    7. {
    8. 	ll t,l,next;
    9. }edge[N<<1];
    10. ll cn=0;
    11. ll head[N];
    12. void add(ll a,ll b,ll c)
    13. {
    14. 	edge[++cn].t=b;
    15. 	edge[cn].l=c;
    16. 	edge[cn].next=head[a];
    17. 	head[a]=cn;
    18. }
    19. struct road
    20. {
    21. 	ll x,y;
    22. 	ll val;
    23. }q[N];
    24. bool cmp(road a,road b)
    25. {
    26. 	return a.val
    27. }
    28. ll siz[N],fa[N],dep[N],top[N],idx[N],a[N],mas[N],son[N];
    29. ll cnt,fir,sec,n,m,rt,x,y,z;
    30. map,ll> mp;
    31. map ms;
    32. void init_dfs(ll id,ll p,ll depth)
    33. {
    34. 	fa[id]=p;
    35. 	siz[id]=1;
    36. 	ms[id]=mp[make_pair(id,p)];//让儿子与边建立映射
    37. 	dep[id]=depth+1;
    38. 	ll son_val=0;
    39. 	for(int i=head[id];i!=-1;i=edge[i].next)
    40. 	{
    41. 		ll y=edge[i].t;
    42. 		if(y==p) continue;
    43. 		init_dfs(y,id,depth+1);
    44. 		siz[id]+=siz[y];
    45. 		if(siz[y]>son_val)
    46. 		{
    47. 			son_val=siz[y];
    48. 			son[id]=y;
    49. 		}
    50. 	}
    51. }
    52. void dfs2(ll id,ll p)
    53. {
    54. 	top[id]=p;
    55. 	idx[id]=++cnt;
    56. 	a[cnt]=mas[id];
    57. 	if(!son[id]) return;
    58. 	dfs2(son[id],p);
    59. 	for(int i=head[id];i!=-1;i=edge[i].next)
    60. 	{
    61. 		ll y=edge[i].t;
    62. 		if(!idx[y]) dfs2(y,y);
    63. 	}
    64. }
    65. ll get_lca(ll x,ll y)
    66. {
    67. 	while(top[x]!=top[y])
    68. 	{
    69. 		if(dep[top[x]]swap(x,y);
    70. 		x=fa[top[x]];
    71. 	}
    72. 	return dep[x]>dep[y]?y:x;
    73. }
    74. ll f[N];
    75. ll find(ll x)
    76. {
    77. 	return f[x]==x?f[x]:f[x]=find(f[x]);
    78. }
    79. ll ans[N];
    80. int main()
    81. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    82. 	memset(head,-1,sizeof head);
    83. 	memset(ans,-1,sizeof ans);
    84. 	cin>>n>>m;
    85. 	for(int i=1;i
    86. 	{
    87. 		cin>>fir>>sec;
    88. 		add(fir,sec,1);
    89. 		add(sec,fir,1);
    90. 		mp[make_pair(fir,sec)]=i;//边与两个点建立映射
    91. 		mp[make_pair(sec,fir)]=i;
    92. 	}
    93. 	rt=1;
    94. 	init_dfs(rt,0,1);
    95. 	dfs2(rt,rt);
    96. 	for(int i=1;i<=m;++i)
    97. 	{
    98. 		cin>>q[i].x>>q[i].y>>q[i].val;
    99. 	}
    100. 	sort(q+1,q+1+m,cmp);
    101. 	for(int i=1;i<=n;++i) f[i]=i;
    102. 	for(int i=1;i<=m;++i)
    103. 	{
    104. 		ll fx=find(q[i].x);ll fy=find(q[i].y);
    105. 		ll LCA=get_lca(fx,fy);
    106. 		while(dep[fx]>dep[LCA])
    107. 		{
    108. 			//cout<
    109. 			ans[ms[fx]]=q[i].val;
    110. 			f[fx]=find(fa[fx]);//注意要跳到父亲节点的对应的第一个可以更新的点
    111. 			fx=f[fa[fx]];
    112. 		} 
    113. 		while(dep[fy]>dep[LCA])
    114. 		{
    115. 			//cout<
    116. 			ans[ms[fy]]=q[i].val;
    117. 			f[fy]=find(fa[fy]);//注意要跳到父亲节点的对应的第一个可以更新的点
    118. 			fy=f[fa[fy]];
    119. 		}
    120. 		
    121. 	}
    122. 	for(int i=1;i
    123. 	return 0;
    124. }

     [SDOI2011]染色

    大意：

    区间覆盖，求区间颜色段数

    思路：

     维护一下线段树的左端点和右端点的颜色，每次合并的时候，让两个子区间的val值相加，如果左儿子的右端点颜色=右儿子左端点颜色，就让val-1即可。

    那么查询的时候，就把每一条经过的重链区间的val相加，同样的，如果某一条链的top的颜色=其父节点的颜色，val-1 

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty
    7. {
    8. 	ll t,l,next;
    9. }edge[N<<1];
    10. ll cn=0;
    11. ll head[N];
    12. void add_edge(ll a,ll b,ll c)
    13. {
    14. 	edge[++cn].t=b;
    15. 	edge[cn].l=c;
    16. 	edge[cn].next=head[a];
    17. 	head[a]=cn;
    18. }
    19. struct tree
    20. {
    21. 	ll l,r;
    22. 	ll lm,rm;
    23. 	ll siz;
    24. 	ll add;
    25. 	ll val; 
    26. }tr[N<<2];
    27. ll siz[N],fa[N],top[N],son[N],a[N],idx[N],mas[N],dep[N];
    28. ll n,m,rt,cnt,fir,sec,x,y,z;
    29. char op;
    30. void init_dfs(ll id,ll p,ll depth)
    31. {
    32. 	dep[id]=depth;
    33. 	fa[id]=p;
    34. 	siz[id]=1;
    35. 	ll son_val=0;
    36. 	for(int i=head[id];i!=-1;i=edge[i].next)
    37. 	{
    38. 		ll y=edge[i].t;
    39. 		if(y==p) continue;
    40. 		init_dfs(y,id,depth+1);
    41. 		siz[id]+=siz[y];
    42. 		if(siz[y]>son_val)
    43. 		{
    44. 			son_val=siz[y];
    45. 			son[id]=y;
    46. 		}
    47. 	}
    48. }
    49. void dfs2(ll id,ll p)
    50. {
    51. 	top[id]=p;
    52. 	idx[id]=++cnt;
    53. 	a[cnt]=mas[id];
    54. 	if(!son[id]) return;
    55. 	dfs2(son[id],p);
    56. 	for(int i=head[id];i!=-1;i=edge[i].next)
    57. 	{
    58. 		ll y=edge[i].t;
    59. 		if(!idx[y]) dfs2(y,y);
    60. 	}
    61. }
    62. void push_up(ll p)
    63. {
    64. 	tr[p].val=tr[p<<1].val+tr[p<<1|1].val;
    65. 	if(tr[p<<1].rm==tr[p<<1|1].lm) tr[p].val-=1;
    66. 	tr[p].lm=tr[p<<1].lm;
    67. 	tr[p].rm=tr[p<<1|1].rm;
    68. }
    69. void push_down(ll p)
    70. {
    71. 	if(tr[p].add==0) return;
    72. 	tr[p<<1].add=tr[p<<1|1].add=tr[p].add;
    73. 	tr[p<<1].lm=tr[p<<1].rm=tr[p].add;
    74. 	tr[p<<1|1].lm=tr[p<<1|1].rm=tr[p].add;
    75. 	tr[p<<1].val=tr[p<<1|1].val=1;
    76. 	tr[p].add=0;
    77. }
    78. void build(ll p,ll l,ll r)
    79. {
    80. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    81. 	if(l==r)
    82. 	{
    83. 		tr[p].val=1;
    84. 		tr[p].lm=tr[p].rm=a[l];
    85. 		return;
    86. 	}
    87. 	ll mid=l+r>>1;
    88. 	build(p<<1,l,mid);
    89. 	build(p<<1|1,mid+1,r);
    90. 	push_up(p);
    91. }
    92. void change(ll p,ll l,ll r,ll val)
    93. {
    94. 	if(tr[p].l>=l&&tr[p].r<=r)
    95. 	{
    96. 		tr[p].val=1;
    97. 		tr[p].lm=tr[p].rm=val;
    98. 		tr[p].add=val;
    99. 		return;
    100. 	}
    101. 	push_down(p);
    102. 	ll mid=tr[p].l+tr[p].r>>1;
    103. 	if(r<=mid)
    104. 	{
    105. 		change(p<<1,l,r,val);
    106. 	}
    107. 	else if(l>mid)
    108. 	{
    109. 		change(p<<1|1,l,r,val);
    110. 	}
    111. 	else
    112. 	{
    113. 		change(p<<1,l,r,val);
    114. 		change(p<<1|1,l,r,val);
    115. 	}
    116. //	if(l<=mid) change(p<<1,l,r,val);
    117. //	if(r>mid) change(p<<1|1,l,r,val);
    118. 	push_up(p);
    119. }
    120. ll sum(ll p,ll l,ll r)
    121. {
    122. 	if(tr[p].l>=l&&tr[p].r<=r)
    123. 	{
    124. 		return tr[p].val;
    125. 	}
    126. 	push_down(p);
    127. 	ll mid=tr[p].l+tr[p].r>>1;
    128. 	ll ans=0;
    129. 	if(r<=mid) return sum(p<<1,l,r);
    130. 	if(l>mid) return sum(p<<1|1,l,r);
    131. 	ans+=sum(p<<1,l,r);ans+=sum(p<<1|1,l,r);
    132. 	if(tr[p<<1].rm==tr[p<<1|1].lm) ans--;
    133. 	return ans;
    134. }
    135. ll col(ll p,ll l)
    136. {
    137. 	if(tr[p].l==tr[p].r&&tr[p].l==l)
    138. 	{
    139. 		return tr[p].lm;
    140. 	}
    141. 	push_down(p);
    142. 	ll mid=tr[p].l+tr[p].r>>1;
    143. 	if(l<=mid) return col(p<<1,l);
    144. 	else return col(p<<1|1,l);
    145. }
    146. void tree_change(ll x,ll y,ll val)
    147. {
    148. 	while(top[x]!=top[y])
    149. 	{
    150. 		if(dep[top[x]]swap(x,y);
    151. 		change(1,idx[top[x]],idx[x],val);
    152. 		x=fa[top[x]];
    153. 	}
    154. 	if(dep[x]>dep[y]) swap(x,y);
    155. 	change(1,idx[x],idx[y],val);
    156. }
    157. ll tree_sum(ll x,ll y)
    158. {
    159. 	ll ans=0;
    160. 	while(top[x]!=top[y])
    161. 	{
    162. 		if(dep[top[x]]swap(x,y);
    163. 		ans+=sum(1,idx[top[x]],idx[x]);
    164. 		if(col(1,idx[top[x]])==col(1,idx[fa[top[x]]])) ans--;
    165. 		x=fa[top[x]];
    166. 	}
    167. 	if(dep[x]>dep[y]) swap(x,y);
    168. 	ans+=sum(1,idx[x],idx[y]);
    169. 	return ans;
    170. }
    171. int main()
    172. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    173. 	//注意push_up时对左右边界的更新 
    174. 	memset(head,-1,sizeof head);
    175. 	cin>>n>>m;
    176. 	for(int i=1;i<=n;++i) cin>>mas[i];
    177. 	for(int i=1;i
    178. 	{
    179. 		cin>>fir>>sec;
    180. 		add_edge(fir,sec,1);
    181. 		add_edge(sec,fir,1);
    182. 	}
    183. 	rt=1;
    184. 	init_dfs(rt,0,1);
    185. 	dfs2(rt,rt);
    186. 	build(1,1,n);
    187. //	cout<
    188. 	while(m--)
    189. 	{
    190. 		cin>>op;
    191. 		if(op=='C')
    192. 		{
    193. 			cin>>x>>y>>z;
    194. 			tree_change(x,y,z);
    195. 			continue;
    196. 		}
    197. 		cin>>x>>y;
    198. 		cout<<tree_sum(x,y)<
    199. 	}
    200. }

    遥远的国度

    大意：

    换根，区间覆盖，查询子树最小值 

    思路：

    讲一下换根。其实跟第一题的区别不算很大 

    令root为当前根，x为要求的根，lca为两者的lca

    1.u==root：直接输出整棵树的最小值就可以了

    2.lca!=x:x的子树没有变，就正常查询就可以了

    3.lca==x:x的子树就变成了x到root路径上第一个儿子的子树的补集，考虑到子树的dfn序是连续的，所以我们可以把查询区间分成两个部分，一个是dfn序小于第一个儿子子树dfn序的区间，一个是dfn序大于第一个儿子子树dfn序的区间。然后合并求最小值就可以了啦

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty
    7. {
    8. 	ll t,l,next;
    9. }edge[N<<1];
    10. ll cn=0;
    11. ll head[N];
    12. void add_edge(ll a,ll b,ll c)
    13. {
    14. 	edge[++cn].t=b;
    15. 	edge[cn].l=c;
    16. 	edge[cn].next=head[a];
    17. 	head[a]=cn;
    18. }
    19. struct tree
    20. {
    21. 	ll l,r;
    22. 	ll siz;
    23. 	ll add=-1;
    24. 	ll val;
    25. }tr[N<<2];
    26. ll siz[N],fa[N],son[N],dep[N],idx[N],a[N],mas[N],top[N];
    27. ll n,m,rt,cnt,fir,sec,x,y,z,op;
    28. void init_dfs(ll id,ll p,ll depth)
    29. {
    30. 	dep[id]=depth;
    31. 	fa[id]=p;
    32. 	siz[id]=1;
    33. 	ll son_val=0;
    34. 	for(int i=head[id];i!=-1;i=edge[i].next)
    35. 	{
    36. 		ll y=edge[i].t;
    37. 		if(y==p) continue;
    38. 		init_dfs(y,id,depth+1);
    39. 		siz[id]+=siz[y];
    40. 		if(siz[y]>son_val)
    41. 		{
    42. 			son_val=siz[y];
    43. 			son[id]=y;
    44. 		}
    45. 	}
    46. }
    47. void dfs2(ll id,ll p)
    48. {
    49. 	top[id]=p;
    50. 	idx[id]=++cnt;
    51. 	a[cnt]=mas[id];
    52. 	if(!son[id]) return;
    53. 	dfs2(son[id],p);
    54. 	for(int i=head[id];i!=-1;i=edge[i].next)
    55. 	{
    56. 		ll y=edge[i].t;
    57. 		if(!idx[y]) dfs2(y,y);
    58. 	}
    59. }
    60. void push_up(ll p)
    61. {
    62. 	tr[p].val=min(tr[p<<1].val,tr[p<<1|1].val);
    63. }
    64. void push_down(ll p)
    65. {
    66. 	if(tr[p].add==-1) return;
    67. 	tr[p<<1].add=tr[p<<1|1].add=tr[p].add;
    68. 	tr[p<<1].val=tr[p<<1|1].val=tr[p].add;
    69. 	tr[p].add=-1;
    70. }
    71. void build(ll p,ll l,ll r)
    72. {
    73. 	tr[p].l=l;tr[p].r=r;tr[p].siz=r-l+1;
    74. 	if(l==r)
    75. 	{
    76. 		tr[p].val=a[l];
    77. 		return;
    78. 	}
    79. 	ll mid=r+l>>1;
    80. 	build(p<<1,l,mid);
    81. 	build(p<<1|1,mid+1,r);
    82. 	push_up(p); 
    83. }
    84. void change(ll p,ll l,ll r,ll val)
    85. {
    86. 	if(tr[p].l>=l&&tr[p].r<=r)
    87. 	{
    88. 		tr[p].add=tr[p].val=val;
    89. 		return;
    90. 	}
    91. 	push_down(p);
    92. 	ll mid=tr[p].l+tr[p].r>>1;
    93. 	if(l<=mid) change(p<<1,l,r,val);
    94. 	if(r>mid) change(p<<1|1,l,r,val);
    95. 	push_up(p);
    96. }
    97. void tree_change(ll x,ll y,ll val)
    98. {
    99. 	while(top[x]!=top[y])
    100. 	{
    101. 		if(dep[top[x]]swap(x,y);
    102. 		change(1,idx[top[x]],idx[x],val); 
    103. 		x=fa[top[x]];
    104. 	}
    105. 	if(dep[x]>dep[y]) swap(x,y);
    106. 	change(1,idx[x],idx[y],val);
    107. }
    108. ll sum(ll p,ll l,ll r)
    109. {
    110. 	if(tr[p].l>=l&&tr[p].r<=r)
    111. 	{
    112. 		return tr[p].val;
    113. 	}
    114. 	ll ans=1e16;
    115. 	push_down(p);
    116. 	ll mid=tr[p].l+tr[p].r>>1;
    117. 	if(l<=mid) ans=min(ans,sum(p<<1,l,r));
    118. 	if(r>mid) ans=min(ans,sum(p<<1|1,l,r));
    119. 	return ans;
    120. }
    121. ll get_lca(ll x,ll y)
    122. {
    123. 	while(top[x]!=top[y])
    124. 	{
    125. 		if(dep[top[x]]swap(x,y);
    126. 		x=fa[top[x]];
    127. 	}
    128. 	return dep[x]>dep[y]?y:x;
    129. }
    130. ll find_firson(ll x,ll y)//找打x到y路径上的第一个儿子 
    131. {
    132. 	while(top[x]!=top[y])
    133. 	{
    134. 		if(dep[top[x]]swap(x,y);
    135. 		if(fa[top[x]]==y) return top[x];
    136. 		x=fa[top[x]];
    137. 	} 
    138. 	if(dep[x]>dep[y]) swap(x,y); 
    139. 	return son[x];
    140. }
    141. ll trson_sum(ll x)
    142. {
    143. 	if(x==rt) return sum(1,1,n);
    144. 	ll LCA=get_lca(x,rt);
    145. 	if(LCA!=x) return sum(1,idx[x],idx[x]+siz[x]-1);
    146. 	ll fir_son=find_firson(x,rt);
    147. 	ll ans1=sum(1,1,idx[fir_son]-1);
    148. 	ll ans2=sum(1,idx[rt]+siz[rt],n);
    149. 	return min(ans1,ans2);
    150. }
    151. int main()
    152. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
    153. 	memset(head,-1,sizeof head);
    154. 	cin>>n>>m;
    155. 	for(int i=1;i
    156. 	{
    157. 		cin>>fir>>sec;
    158. 		add_edge(fir,sec,1);
    159. 		add_edge(sec,fir,1);
    160. 	} 
    161. 	for(int i=1;i<=n;++i) cin>>mas[i];
    162. 	cin>>rt;
    163. 	init_dfs(1,0,1);
    164. 	dfs2(1,1);
    165. 	build(1,1,n);
    166. 	while(m--)
    167. 	{
    168. 		cin>>op;
    169. 		if(op==1)
    170. 		{
    171. 			cin>>x;
    172. 			rt=x;
    173. 			continue;
    174. 		}
    175. 		else if(op==2)
    176. 		{
    177. 			cin>>x>>y>>z;
    178. 			tree_change(x,y,z);
    179. 			continue;
    180. 		}
    181. 		else
    182. 		{
    183. 			cin>>x;
    184. 			cout<<trson_sum(x)<
    185. 		}
    186. 	}
    187. }

    [USACO19DEC]Milk Visits G

    大意：

    对一段区间，查询是否存在特定值

    思路：

    直接维护所有颜色是不现实的，所以不妨将答案离线下来，按大小升序排序。那么，每次遍历到一种颜色的时候，我们再在线段树上更新对应的颜色，如此，我们只要维护区间最大值就可以了，如果最大值=颜色，就是可以的，否则一定不行，那么就没了（还是钻了没有修改操作的空子嘿嘿） 

    1. #include
    2. using namespace std;
    3. #define ll long long
    4. #define endl '\n'
    5. const ll N=1e5+10;
    6. struct ty
    7. {
    8. 	ll t,l,next;
    9. }edge[N<<1];
    10. ll cn=0;
    11. ll head[N]; 
    12. void add_edge(ll a,ll b,ll c)
    13. {
    14. 	edge[++cn].t=b;
    15. 	edge[cn].l=c;
    16. 	edge[cn].next=head[a];
    17. 	head[a]=cn;
    18. }
    19. struct tree
    20. {
    21. 	ll l,r;
    22. 	ll val;
    23. 	ll add;
    24. 	ll siz;
    25. }tr[N<<2];
    26. vector color[N];
    27. ll siz[N],dep[N],top[N],fa[N],son[N],a[N],mas[N],idx[N];
    28. ll n,m,fir,sec,cnt,x,y,z,rt;
    29. ll ans[N];
    30. bool vis[N];
    31. struct query
    32. {
    33. 	ll x,y,z;
    34. 	ll id;
    35. }q[N];
    36. bool cmp(query a,query b)
    37. {
    38. 	return a.z
    39. }
    40. void init_dfs(ll id,ll p,ll depth)
    41. {
    42. 	dep[id]=depth;
    43. 	fa[id]=p;
    44. 	siz[id]=1;
    45. 	ll son_val=0;
    46. 	for(int i=head[id];i!=-1;i=edge[i].next)
    47. 	{
    48. 		ll y=edge[i].t;
    49. 		if(y==p) continue;
    50. 		init_dfs(y,id,depth+1);
    51. 		siz[id]+=siz[y];
    52. 		if(siz[y]>son_val)
    53. 		{
    54. 			son_val=siz[y];
    55. 			son[id]=y;
    56. 		}
    57. 	}
    58. }
    59. void dfs2(ll id,ll p)
    60. {
    61. 	top[id]=p;
    62. 	idx[id]=++cnt;
    63. 	a[cnt]=mas[id];
    64. 	if(!son[id]) return;
    65. 	dfs2(son[id],p);
    66. 	for(int i=head[id];i!=-1;i=edge[i].next)
    67. 	{
    68. 		ll y=edge[i].t;
    69. 		if(!idx[y]) dfs2(y,y);
    70. 	}
    71. }
    72. void push_up(ll p)
    73. {
    74. 	tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
    75. }
    76. void build(ll p,ll l,ll r)
    77. {
    78. 	tr[p].l=l;tr[p].r=r;
    79. 	tr[p].siz=r-l+1;
    80. 	if(l==r){
    81. 		tr[p].val=a[l];
    82. 		return;
    83. 	}
    84. 	ll mid=tr[p].l+tr[p].r>>1;
    85. 	build(p<<1,l,mid);
    86. 	build(p<<1|1,mid+1,r);
    87. 	push_up(p);
    88. }
    89. void change(ll p,ll l,ll r,ll val)
    90. {
    91. 	if(tr[p].l>=l&&tr[p].r<=r)
    92. 	{
    93. 		tr[p].val=val;
    94. 		return;
    95. 	}
    96. 	ll mid=tr[p].l+tr[p].r>>1;
    97. 	if(l<=mid) change(p<<1,l,r,val);
    98. 	if(r>mid) change(p<<1|1,l,r,val);
    99. 	push_up(p); 
    100. }
    101. ll sum(ll p,ll l,ll r,ll val)
    102. {
    103. 	if(tr[p].l>=l&&tr[p].r<=r)
    104. 	{
    105. 		return tr[p].val==val;
    106. 	}
    107. 	ll mid=tr[p].l+tr[p].r>>1;
    108. 	if(l<=mid) if(sum(p<<1,l,r,val)) return 1;
    109. 	if(r>mid) if(sum(p<<1|1,l,r,val)) return 1;
    110. 	return 0;
    111. }
    112. ll tree_sum(ll x,ll y,ll val)
    113. {
    114. 	while(top[x]!=top[y])
    115. 	{
    116. 		if(dep[top[x]]swap(x,y);
    117. 		if(sum(1,idx[top[x]],idx[x],val)) return 1;
    118. 		x=fa[top[x]];
    119. 	}
    120. 	if(dep[x]>dep[y]) swap(x,y);
    121. 	if(sum(1,idx[x],idx[y],val)) return 1;
    122. 	return 0;
    123. }
    124. int main()
    125. {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    126. 	memset(head,-1,sizeof head);
    127. 	cin>>n>>m;
    128. 	for(int i=1;i<=n;++i)
    129. 	{
    130. 		cin>>x;
    131. 		color[x].push_back(i);
    132. 	}
    133. 	for(int i=1;i
    134. 	{
    135. 		cin>>fir>>sec;
    136. 		add_edge(fir,sec,1);
    137. 		add_edge(sec,fir,1);
    138. 	}
    139. 	for(int i=1;i<=m;++i)
    140. 	{
    141. 		cin>>q[i].x>>q[i].y>>q[i].z;
    142. 		q[i].id=i;
    143. 	}
    144. 	rt=1;
    145. 	init_dfs(rt,0,1);
    146. 	dfs2(rt,rt);
    147. 	build(1,1,n);
    148. 	sort(q+1,q+1+m,cmp);
    149. 	for(int i=1;i<=m;++i)
    150. 	{
    151. 		ll col=q[i].z;
    152. 		if(color[col].size()==0) continue;
    153. 		if(!vis[col])
    154. 		{
    155. 			for(int k:color[col])
    156. 			{
    157. 				change(1,idx[k],idx[k],col);
    158. 			}
    159. 		}
    160. 		vis[col]=1;
    161. 		ans[q[i].id]=tree_sum(q[i].x,q[i].y,q[i].z);
    162. 	}
    163. 	for(int i=1;i<=m;++i) cout<
    164. }

    更新中...

  • 相关阅读:
    火热报名中 | 2天峰会、20+热门议题，AutoESG 2023数智低碳---中国汽车碳管理创新峰会亮点抢先看！
    Excel 导出打不开
    使用ES检索PDF或Word等格式文件方案
    Pytest系列（31） - config.cache 使用
    00Hadoop数据仓库平台
    论文笔记 - SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios
    【MySQL】MySQL数据库锁使用与InnoDB加锁的原理解析（MySQL专栏启动）
    关于队头阻塞的一些笔记
    ONLYOFFICE 文档 8.1 现已发布：功能全面的 PDF 编辑器、幻灯片版式等等
    STM32 定时器问题
  • 原文地址：https://blog.csdn.net/sophilex/article/details/126746589