最大化access轻重链的切换次数
考虑一个点的贡献，即它交换重儿子的次数
发现这个次数只和它自己ai以及每个儿子的子树次数和有关。
一个关键的事实是：
我们可以自上而下进行贪心！
我们最大化fa的贡献，发现，对于操作序列，一个儿子子树的操作是一个子序列，不影响这个儿子子树的贡献！
（内部可以任意交换）
等价于：有m=|son|+1种颜色，每种颜色有若干个
排成一列，最大化相邻不相同颜色的次数
设颜色最多的是h，总和为t
则次数=min(t-1,2*(t-h))
证明的话：考虑先放那最多的h个然后插空，对于剩下的p=(t-h)个，如果p<=h-1，那么显然直接插空，贡献2*p个，如果p>h-1，那么一定可以不断来回插空，达到上界t-1
已经可以做不修改的了。
修改：
关键：1.只加w。2.考虑临界情况：2*h>=t+1时候，贡献2*(t-h)，否则贡献t-1。3.仅影响到根的链答案
如果一个点可以作为fa的最大值来源，则把这个链变成实链。
发现，修改一个点x时候，往上跳，实链还是实链，并且贡献还是不变的！
所以，只用考虑虚边的影响
发现，每跳一个虚边，所在子树的S*=2，所以最多log∑ai个
修改虚边：
减去原来的贡献，加上新来的贡献，分类讨论
用LCT的access实现跳跃实链
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}
template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{
const int N=4e5+;
int n,m;
struct node{
int nxt,to;
}e[*N];
int hd[N],cnt;
ll ans;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
struct tr{
int ch[],fa;
ll v,s,si;
void out(){
cout<<" ch0 "<<ch[]<<" ch1 "<<ch[]<<" fa "<<fa<<endl;
cout<<" v "<<v<<" s "<<s<<" si "<<si<<endl;
}
}t[N];
#define ls t[x].ch[0]
#define rs t[x].ch[1]
bool nrt(int x){
return t[t[x].fa].ch[]==x||(t[t[x].fa].ch[]==x);
}
void pushup(int x){
if(x) t[x].s=t[ls].s+t[rs].s+t[x].si+t[x].v;
}
void rotate(int x){
int y=t[x].fa,d=t[y].ch[]==x;
t[t[y].ch[d]=t[x].ch[!d]].fa=y;
if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[]==y]=x;
else t[x].fa=t[y].fa;
t[t[x].ch[!d]=y].fa=x;
pushup(y);
}
void splay(int x){
while(nrt(x)){
int y=t[x].fa,z=t[y].fa;
if(nrt(y)){
rotate((t[y].ch[]==x)==(t[z].ch[]==y)?y:x);
}
rotate(x);
}
pushup(x);
}
void dfs(int x,int fa){
ll mx=t[x].v;t[x].s=t[x].v;
int p=x;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
t[y].fa=x;
dfs(y,x);
t[x].s+=t[y].s;
t[x].si+=t[y].s;
if(t[y].s>mx){
mx=t[y].s;p=y;
}
}
if(*mx>=t[x].s+){
if(p!=x) {
rs=p;t[x].si-=t[p].s;
}
}
ans+=min(t[x].s-,*(t[x].s-mx));
} int main(){
int m;
rd(n);rd(m);
for(reg i=;i<=n;++i){
rd(t[i].v);
}
int x,y;
for(reg i=;i<n;++i){
rd(x);rd(y);
add(x,y);add(y,x);
}
dfs(,);
printf("%lld\n",ans);
ll w;
// for(reg i=1;i<=n;++i){
// cout<<i<<" : ";t[i].out();
// }cout<<endl; while(m--){
rd(x);rd(w);
for(reg y=;x;y=x,x=t[x].fa){
splay(x);
ll S=t[x].s-t[ls].s;
// cout<<" x "<<x<<" y "<<y<<" S "<<S<<endl;
ll con=rs?min(S-,*(S-t[rs].s)):min(S-,*(S-t[x].v));
// cout<<" con "<<con<<endl;
ans-=con;
if(!y) {
t[x].v+=w;S+=w;t[x].s+=w;
}else{
t[x].si+=w;S+=w;t[x].s+=w;
}
// cout<<" out ";t[x].out();
if(y){
if(rs){
if(*t[rs].s<S+&&*t[y].s<S+){
ans+=S-;
t[x].si+=t[rs].s;
rs=;
}else if(*t[rs].s>*t[y].s){
ans+=*(S-t[rs].s);
}else{
ans+=*(S-t[y].s);
t[x].si+=t[rs].s;
t[x].si-=t[y].s;
rs=y;
}
}else{
if(*t[x].v<S+&&*t[y].s<S+){
ans+=S-;
}else if(*t[x].v>*t[y].s){
ans+=*(S-t[x].v);
}else{
ans+=*(S-t[y].s);
t[x].si-=t[y].s;
rs=y;
}
}
}else{
if(rs){
if(*t[rs].s<S+&&*t[x].v<S+){
ans+=S-;
t[x].si+=t[rs].s;
rs=;
}else if(*t[rs].s>*t[x].v){
ans+=*(S-t[rs].s);
}else{
ans+=*(S-t[x].v);
t[x].si+=t[rs].s;
rs=;
}
}else{
if(*t[x].v<S+&&*t[y].s<S+){
ans+=S-;
}else if(*t[x].v>*t[y].s){
ans+=*(S-t[x].v);
}else{
ans+=*(S-t[y].s);
t[x].si-=t[y].s;
rs=y;
}
}
}
pushup(x);
}
printf("%lld\n",ans);
}
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/4/13 19:58:12
*/
1.考虑每个点的贡献！把题意进行转化
2.修改时候，考虑具体影响的部分是哪些。