题目描述
有一个一号点为根的有根树 初始时所有点均无颜色。
定义对某个点的操作是将这个点到根的所有路径涂上和这个点编号相同的颜色。定义一次这样的操作的收益是这个点到根上的路径与这个点颜色不同的颜色种类个数（未涂过的不算）
现在你知道了每个点最多只行了多少次这种操作 让你安排一种操作顺序 使得收益最大。带修改。
题解
这个题意看起来花里胡哨，我们先考虑如何转化这个题意。
每个点到根的路径涂上新颜色 这个操作看起来就像是 LCT 的 access 操作，也就是我们每一棵 Splay 都维护颜色相同的边组成的一条链。并且这些颜色也是连续的一块 所以操作一个点的贡献就是 access 过程中虚实边更换的次数。
那么现在题目变成了：让你安排一个access的顺序 使得虚实边切换次数最大。想到这里我们还是只能获得 10 分的好成绩。
对于这种看起来操作次数非常大的 肯定方案构造出来是可以快速计算次数的 不可能挨个操作。所以我们观察一下这个操作有什么性质。
考虑一个点的子树内的最优操作序列确定好了之后 一定是以插入的方式插入到祖先的最优操作序列中。也就是每个点是独立的。
那么我们单独考虑每一个点，这个点的实子边能被切换 只有可能是子树里的点的操作会影响（其他的子树操作会钦定一个新边为实的，这个点操作会让所有的子边都变虚）。但是发现如果操作这个实边对应的子树里面的边就不会有任何贡献。所以我们肯定尽量把不同子树的边交叉使用。发现匹配不出当且仅当某一个子树（或者这个点）可以使用的次数大于和的一半，所以答案可以表示成（记 $S_x$ 表示子树和，$a_x$ 表示点的权值，$\text{son}_x$ 表示 $x$ 的子节点$\min\{S_x-1,2*(S_x-\max_{y \in \text{son}_x} S_y)\}$。其中当 $2*\max_{y \in \text{son}_x} S_y > S_x$ 的时候取后者（注意上面都没有讨论点 $x$ 因为公式不是很好写）。
那么如果不带修改 dfs 一遍就可以解决问题。现在我们考虑如何支持修改（剩下部分的我完全想不出来了）：
我们修改一个点只会影响这个点到根路径上的所有点对答案的贡献。那么我们发现如果修改的点所在的子树本身就是不能被匹配完的 那么加上去的这些不会造成任何贡献。所以这启发我们把所有边满足儿子超过父亲一半的边都变成实边，其他的变成虚边（类似轻重链剖分）。联想轻重链剖分的性质可以发现一个点到根的路径上只会有 $\log a_i$ 条虚边。我们用 LCT 维护（这里不要和一开始提到的弄混了 一开始提到的只是为了帮助转化题意 实际上并不需要维护出来）。每次操作一段实链对答案的贡献都不会改变 只有轻边才会变。那我们可以类似 LCT access 的写法 只是这里虚实边切换只有在 > $\frac{S_x}{2}$ 的点换了之后切换，而不是之前那种无脑切换。
总之这道题好神啊。。。虽然代码十分短
Code:
#include<bits/stdc++.h>
#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5e5 + 5;
int ch[MAXN][2],f[MAXN];
LL sm[MAXN],smi[MAXN],a[MAXN];
#define lc (ch[x][0])
#define rc (ch[x][1])
inline void pushup(int x){sm[x] = sm[lc]+sm[rc]+smi[x]+a[x];}
inline bool nroot(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline void rotate(int x){
int y = f[x],z = f[y],k = ch[y][1]==x,w = ch[x][!k];
if(nroot(y)) ch[z][ch[z][1]==y]=x;f[x]=z;
ch[x][!k] = y;f[y] = x;ch[y][k] = w;if(w) f[w] = y;
pushup(y);pushup(x);
}
inline void splay(int x){
while(nroot(x)){
int y = f[x],z = f[y];
if(nroot(y)) rotate((ch[z][1]==y)^(ch[y][1]==x)?x:y);
rotate(x);
}
pushup(x);
}
std::vector<int> G[MAXN];
int tp[MAXN];LL ans;
//0: 子树大 1:自己大 2: 都不大
inline void dfs(int v,int fa=0){
LL mx = a[v];int mp = v;
for(auto x:G[v]){
if(x == fa) continue;
f[x] = v;dfs(x,v);
smi[v] += sm[x];
if(mx < sm[x]) mx = sm[x],mp = x;
}
sm[v] = smi[v]+a[v];
if((mx<<1) > sm[v]){
ans += (sm[v]-mx)<<1;
if(mp == v) tp[v] = 1;
else smi[v] -= sm[mp],ch[v][1] = mp;
}
else tp[v] = 2,ans += sm[v]-1;
}
inline void access(int x,int w){ // add w
for(int y = 0;x;x = f[y = x]){// 这里的y的意思就是这次加法操作是从哪个虚子树加上来的
splay(x);
LL S = sm[x]-sm[lc];//子树和
if(tp[x] == 0) ans -= (S-sm[rc])<<1;//这里rc就不会有lc了
else if(tp[x] == 1) ans -= (S-a[x])<<1;
else ans -= S-1;
S += w;sm[x] += w;
if(y) smi[x] += w;
else a[x] += w;
if(sm[y]<<1 > S) smi[x] += sm[rc]-sm[y],rc = y;
if(sm[rc]<<1 > S) tp[x] = 0,ans += (S-sm[rc])<<1; // 子树过大
else{
if(rc) smi[x] += sm[rc],rc = 0;//实->虚
if(a[x]<<1 > S) tp[x] = 1,ans += (S-a[x])<<1;
else tp[x] = 2,ans += S-1;
}
}
}
int n,m;
int main(){
scanf("%d%d",&n,&m);
FOR(i,1,n) scanf("%lld",a+i);
FOR(i,2,n){
int u,v;scanf("%d%d",&u,&v);G[u].pb(v);G[v].pb(u);
}
dfs(1);printf("%lld\n",ans);
FOR(i,1,m){
int x,w;scanf("%d%d",&x,&w);
access(x,w);printf("%lld\n",ans);
}
return 0;
}