洛谷P4338 [ZJOI2018]曆史（LCT，樹形DP，樹鍊剖分）

洛谷題目傳送門

ZJOI的考場上最弱外省選手T2 10分成功滾粗。。。。。。

首先要想到30分的結論

說實話Day1前幾天剛剛剛掉了SDOI2017的樹點塗色，考場上也想到了這一點

想到了又有什麼用？反正想不到最大的貢獻是怎麼推出來的

然後晚上心中懷着九條CNM看完了Solution.pdf

貌似對我這個蒟蒻來說也隻有這一題可做了。。。。。。

已知書上每個點access的總次數，構造出一個順序，最大化虛實邊的切換總次數

其實如果能發現最優順序的構造是沒有後效性的話，問題便可以進一步簡化

考慮每個點的子樹。假設已經對所有子樹中的點構造出了一個最優順序（一個序列），那麼一定不會和它的所有祖先的子樹中的最優序列産生沖突。這個并不好證明，仔細想一想應該能發現。

于是就可以單獨考慮每個點\(x\)。能對\(x\)的實子邊産生影響的是x的所有子樹和\(x\)本身（access(x)會使\(x\)沒有實子邊），每切換一次都會使答案\(+1\)。顯然同一個子樹中産生的影響是相同的。于是我們要讓來自不同子樹（或\(x\)本身）盡可能交替access。當沒有某個子樹（或\(x\)本身）的\(a\)總和過大時，可以構造出使得（除了第一次）每一次access都有貢獻的方案。如果某個子樹（或\(x\)本身）的\(a\)總和過大，大于所有子樹總和的一半時，是不可以的，那個子樹（或\(x\)本身）的某幾次操作肯定不會有貢獻。用數學公式大概表示每個點的貢獻為（\(S\)為子樹的\(a\)之和，\(c\)為\(x\)的每個子樹）

\[\min\{S_x-1,2*(S_x-\max\{a_x,\forall S_c\})\}

\]

當\(\max\{a_x,\forall S_c\}\gt {S_x+1\over2}\)時\(\min\)取後者

用樹形DP算出來就有30分了

那麼怎樣快速修改呢？

首先，對某個點的\(a\)加上一個值\(w\)，隻可能會影響該點到根的路徑上的點的貢獻。

因為是加一個值，是以假如這些點中某些點的子樹\(S\)大于它父親子樹\(S\)的一半，那麼\(S_x+w\)，\(\max\{a_x,\forall S_c\}\)也會\(+w\)，帶入上式發現貢獻是不變的！

看到某個子樹S大于所有子樹總和的一半，有沒有想到樹剖？樹剖的輕重邊就是這樣劃分的啊！（反正我這種蒟蒻就是想不到）

同樣對維護好每個點子樹S的樹進行輕重鍊剖分，某些點的子樹a之和大于它父親子樹a之和的一半就連重邊（否則連輕邊），這樣每個點至多有一個重兒子。類似樹剖的證明，每個點到根的輕邊總數（也就是我們可能會修改的點數）是\(\log\sum a\)級别的！

修改的複雜度也有保障啦！我們隻要快速找到這些點就好了。用實鍊剖分維護子樹資訊即可（應該不能叫LCT吧，沒有makeroot，link和cut，對于這個問題蒟蒻的LCT總結對LCT的概念也改了改，歡迎Julao們指正！）。全局儲存ans，每次進行類access操作找到虛邊，就讓ans直接減去以前的貢獻，加上w以後判斷目前的情況決定是否要切換虛實邊并讓ans加上新的貢獻即可。

為了友善計算以前的貢獻，蒟蒻覺得可以儲存一下以前貢獻的類型（無非就三種，某子樹過大、自己過大、都不是很大）算的時候就省去了一些判斷的時間。

代碼細節巨多，尤其是類access更新答案那部分。是以就算考場上想到了一些東西，我這種蒟蒻也未必寫得出來吧！瘋狂膜拜考場切T2的laofu爺Orzzzzzzzzzzzz！

#include<cstdio>
#define RG register
#define R RG int
#define I inline void
#define lc c[x][0]
#define rc c[x][1]
#define G ch=getchar()
typedef long long L;
const int N=400009,M=N<<1;
int f[N],c[N][2],he[N],ne[M],to[M];
L ans,a[N],si[N],s[N];
short tp[N];
bool r[N];
template<typename T>
I in(RG T&x){
	RG char G;
	while(ch<'-')G;
	x=ch&15;G;
	while(ch>'-')x*=10,x+=ch&15,G;
}
inline bool nroot(R x){
	return c[f[x]][0]==x||c[f[x]][1]==x;
}
I up(R x){
	s[x]=s[lc]+s[rc]+si[x]+a[x];
}
I rot(R x){
	R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
	if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
	up(f[w]=y);f[y]=x;f[x]=z;
}
I splay(R x){
	R y;
	while(nroot(x)){
		if(nroot(y=f[x]))
			rot((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
		rot(x);
	}
	up(x);
}
void dp(R x){//dp預處理答案
	R y,i,mp=x;
	RG L mx=a[x];
	for(i=he[x];i;i=ne[i]){
		if(f[x]==(y=to[i]))continue;
		f[y]=x;dp(y);
		si[x]+=s[y];
		if(mx<s[y])mx=s[y],mp=y;
	}
	if(mx<<1>(s[x]=si[x]+a[x])){
		ans+=(s[x]-mx)<<1;
		if(x!=mp)si[x]-=s[rc=mp];//子樹過大
		else tp[x]=1;//自己過大
	}
	else tp[x]=2,ans+=s[x]-1;//都不是很大
}
int main(){
	R n,m,i,p=0,x,y;
	RG L w,S;
	in(n);in(m);
	for(i=1;i<=n;++i)in(a[i]);
	for(i=1;i<n;++i){
		in(x);in(y);
		to[++p]=y;ne[p]=he[x];he[x]=p;
		to[++p]=x;ne[p]=he[y];he[y]=p;
	}
	dp(1);printf("%lld\n",ans);
	while(m--){
		in(x);in(w);
		for(y=0;x;x=f[y=x]){
			splay(x);
			S=s[x]-s[lc];//算原來子樹a總和，注意減s[lc]
			ans-=tp[x]<2?(S-(tp[x]?a[x]:s[rc]))<<1:S-1;
			S+=w;s[x]+=w;(y?si:a)[x]+=w;
			if(s[y]<<1>S)si[x]+=s[rc],si[x]-=s[rc=y];//虛實切換
			if(s[rc]<<1>S)   tp[x]=0,ans+=(S-s[rc])<<1;//子樹過大
			else{
				if(rc)si[x]+=s[rc],rc=0;//沒有子樹過大，一定變虛
				if(a[x]<<1>S)tp[x]=1,ans+=(S-a[x])<<1;//自己過大
				else         tp[x]=2,ans+=S-1,rc=0;//都不是很大
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}