「SCOI 2018 D1T1」Tree

傳送門

problem

在大小為 n n n 的樹上，點從 1 1 1 到 n n n 标号，第 i i i 個點有權值 a i a_i ai​，現在需要支援兩種操作：

• 1 U：詢問從 U 出發的所有簡單路徑中，經過的點權值之和的最大值；
• 2 U V：将 U 的權值修改為 V。

注意空間限制 64M。

資料範圍： 1 ≤ n ≤ 1 0 5 1\le n\le10^5 1≤n≤105， 1 ≤ m ≤ 1 0 5 1\le m\le10^5 1≤m≤105，其中 m m m 為操作的數量。

solution

考慮用 LCT 來維護這個東西，主要就是怎麼維護虛兒子的資訊。

對于 splay 上每個點，記 l m x x / r m x x lmx_x/rmx_x lmxx​/rmxx​ 表示點 x x x 所 “ “ “管轄 ” ” ”的實鍊部分，從鍊頂 / / /鍊底出發，能經過的最大點權和。

然後對每個 x x x 開個 multiset，記一下每個虛兒子的 l m x lmx lmx（隻需要知道虛兒子鍊頂延申的最大距離即可）。

轉移就是，考慮從鍊頂 / / /鍊底出發，最大距離不經過 x x x，或者到 x x x 就止步，或者在實鍊上穿過 x x x，或者從 x x x 穿到輕兒子。具體就看代碼細節吧。

詢問的時候，發現把 u u u 點 access 一下，答案就是 r m x x rmx_x rmxx​。

時間複雜度 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e9;
multiset<int>S[N];
int top(int x)  {return S[x].empty()?-inf:*S[x].rbegin();}
namespace LCT{
	int fa[N],val[N],sum[N],son[N][2],lmx[N],rmx[N];
	bool Get(int x)  {return son[fa[x]][1]==x;}
	bool isroot(int x)  {return (!fa[x])||(son[fa[x]][0]!=x&&son[fa[x]][1]!=x);}
	void pushup(int x){
		sum[x]=sum[son[x][0]]+sum[son[x][1]]+val[x];
		lmx[x]=max(lmx[son[x][0]],sum[son[x][0]]+val[x]+max(0,max(top(x),lmx[son[x][1]])));
		rmx[x]=max(rmx[son[x][1]],sum[son[x][1]]+val[x]+max(0,max(top(x),rmx[son[x][0]])));
	}
	void Rotate(int x){
		int y=fa[x],z=fa[y],k=Get(x),l=son[x][k^1];
		if(!isroot(y))  son[z][Get(y)]=x;fa[x]=z;
		son[y][k]=l,fa[l]=(l?y:0),son[x][k^1]=y,fa[y]=x;
		pushup(y),pushup(x);
	}
	void Splay(int x){
		while(!isroot(x)){
			int y=fa[x];
			if(!isroot(y))  Rotate(Get(x)==Get(y)?y:x);
			Rotate(x);
		}
	}
	void Access(int x){
		for(int i=0;x;x=fa[i=x]){
			Splay(x);
			if(son[x][1])  S[x].insert(lmx[son[x][1]]);
			if(i)  S[x].erase(S[x].find(lmx[i]));
			son[x][1]=i,pushup(x);
		}
	}
}
using namespace LCT;
int n,m;
int main(){
	scanf("%d%d",&n,&m),lmx[0]=rmx[0]=-inf;
	for(int i=2;i<=n;++i)  scanf("%d",&fa[i]);
	for(int i=1;i<=n;++i)  scanf("%d",&val[i]);
	for(int i=n;i>=1;--i)  pushup(i),S[fa[i]].insert(lmx[i]);
	int op,u,v;
	while(m--){
		scanf("%d",&op);
		if(op==1)  scanf("%d",&u),Access(u),Splay(u),printf("%d\n",rmx[u]);
		else  scanf("%d%d",&u,&v),Access(u),Splay(u),val[u]=v;
	}
	return 0;
}