「ZJOI2018」历史（LCT）
\(ZJOI\) 也就数据结构可做了……
题意：给定每个点 \(access\) 次数，使轻重链切换次数最大，带修改。
\(30pts:\)
挺好想的。发现切换次数只跟子树中所有结点的 \(access\) 次数，可以树形 \(dp\)。假设 \(x\) 有 \(m\) 个儿子，每个儿子的 \(access\) 次数为 \(A_i\)，自己为 \(A_0\)，问题转换成有 \(m+1\) 种颜色，问怎么使颜色不同的间隔最多。使 \(sum=\sum_{i=0}^{m}A_i,val=\max_{i=0}^{m}A_i\)，那么答案为 \(\min(sum-1,2\times (sum-val))\)
那么我们把 \(\min\) 拆开，当 \(2\times val>sum\) 时，\(2\times (sum-val)\) 更小，否则 \(sum-1\) 更小。
然后就可以 \(O(n)\) 预处理了。
\(100pts:\)
考虑怎么带修改。
我们暴力跳肯定不行，那可以用 \(LCT\) 模拟这个暴力跳的过程。时间复杂度 \(O(n\log n)\)
\(Code\ below:\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=400000+10;
int n,m,son[maxn],op[maxn];
int ch[maxn][2],fa[maxn];ll w[maxn],sum[maxn],siz[maxn],ans;
int head[maxn],to[maxn<<1],nxt[maxn<<1],tot;
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
void print(ll x){
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
inline void pushup(int x){
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+siz[x]+w[x];
}
inline bool nrt(int x){
return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
}
inline void rotate(int x){
int y=fa[x],z=fa[y],k=(ch[y][1]==x),u=ch[x][k^1];
if(nrt(y)) ch[z][ch[z][1]==y]=x;
ch[y][k]=u;ch[x][k^1]=y;
if(u) fa[u]=y;fa[y]=x;fa[x]=z;
pushup(y);pushup(x);
}
inline void splay(int x){
int y,z;
while(nrt(x)){
y=fa[x],z=fa[y];
if(nrt(y)) rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y);
rotate(x);
}
}
inline void addedge(int x,int y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int f){
fa[x]=f;
ll maxson=-1;
for(int i=head[x],y;i;i=nxt[i]){
y=to[i];
if(y==f) continue;
dfs(y,x);siz[x]+=sum[y];
if(sum[y]>maxson) maxson=sum[y],son[x]=y;
}
sum[x]=siz[x]+w[x];
if((maxson<<1)>sum[x]){
op[x]=0;ans+=(sum[x]-maxson)<<1;
ch[x][1]=son[x];siz[x]-=maxson;
}
else if((w[x]<<1)>sum[x]) op[x]=1,ans+=(sum[x]-w[x])<<1;
else op[x]=2,ans+=sum[x]-1;
}
inline void modify(int x,int z){
ll S;
for(int y=0;x;y=x,x=fa[x]){
splay(x);S=sum[x]-sum[ch[x][0]];
ans-=(op[x]<2)?(S-(op[x]?w[x]:sum[ch[x][1]]))<<1:S-1;
S+=z;sum[x]+=z;y?siz[x]+=z:w[x]+=z;
if((sum[y]<<1)>S) siz[x]+=sum[ch[x][1]]-sum[y],ch[x][1]=y;
if((sum[ch[x][1]]<<1)>S) op[x]=0,ans+=(S-sum[ch[x][1]])<<1;
else {
if(ch[x][1]) siz[x]+=sum[ch[x][1]],ch[x][1]=0;
if((w[x]<<1)>S) op[x]=1,ans+=(S-w[x])<<1;
else op[x]=2,ans+=S-1;
}
}
}
int main()
{
n=read(),m=read();
int x,y;
for(int i=1;i<=n;i++) w[i]=read();
for(int i=1;i<n;i++){
x=read(),y=read();
addedge(x,y),addedge(y,x);
}
dfs(1,0);
print(ans),putchar('\n');
for(int i=1;i<=m;i++){
x=read(),y=read();modify(x,y);
print(ans),putchar('\n');
}
return 0;
}