先来看看不带修改的 $30$ 分做法。

考虑一个简单的情况,就是说 $x$ 点有 $m$ 个儿子,第 $i$ 个儿子的崛起次数为 $a_i$ ,$x$ 的值为 $a_0$ ,那么 $x$ 的子树有两种最优的崛起顺序:

  • 一个一个轮流崛起,一共可以带来 $\sum a_i$ 的贡献,除去第一次的崛起不算贡献,这个顺序的总贡献为 $(\sum a_i)-1$ 。
  • 上面的方案有个缺陷,就是说当一个儿子 $v$ 满足 $\sum_{a_i}<2\times a_v$ ,那么一个一个轮流崛起,最终 $v$ 就会有剩下的崛起次数,这崛起次数不管是多少,也最多会对答案造成 $1$ 的贡献,那么这个时候贡献就变成了 $2\times (\sum a_i-a_v)$ 。

第二种情况为第一种的特判,因此计算 $x$ 的答案时只需要在两者之间取 $\min$ 即可。

然后注意更新 $x$ 的"崛起次数",这里的崛起次数不是题目中给的,而是从 $x$ 以及 $x$ 的子树中崛起往上影响到 $fa_x$ 的次数,也就是说 $x$ 的"崛起次数"其实就是 $x$ 的子树的 $a_i$ 总和。

满分做法用 $lct$ 维护一下即可。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=4e5+2;
int n,m,ch[N][2],fa[N],head[N],cnt;
ll ans,a[N],s[N],c[N],dp[N];
/*c[x] : x的虚子树的s的和*/
struct Edge {int nxt,to;} G[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

inline void add(int u,int v) {G[++cnt]=(Edge){head[u],v},head[u]=cnt;}
void dfs(int u,int p) {/*处理初始答案*/
    fa[u]=p;ll mx=s[u]=a[u];int y=0;
    for(int i=head[u],v;i;i=G[i].nxt)
        if((v=G[i].to)!=p) dfs(v,u),s[u]+=s[v],s[v]>mx?mx=s[v],y=v:0;
    dp[u]=min(s[u]-1,2*(s[u]-mx)),ans+=dp[u];
    if(y&&mx*2>s[u]+1) ch[u][1]=y;/*重儿子*/
    c[u]=s[u]-s[ch[u][1]]-a[u];
} 

bool chk(int x) {return ch[fa[x]][1]==x;}
bool isroot(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void pushup(int x) {s[x]=s[ch[x][0]]+s[ch[x][1]]+c[x]+a[x];}
inline void rotate(int x) {
    int y=fa[x],z=fa[y],k=chk(x),v=ch[x][!k];
    if(isroot(y)) ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
    if(v) fa[v]=y;fa[y]=x,fa[x]=z;pushup(y);
}
inline void Splay(int x) {
    int y;while(isroot(x)) {
        if(isroot(y=fa[x])) rotate((ch[fa[y]][0]==y)^(ch[y][0]==x)?x:y);
        rotate(x);
    }pushup(x); 
}
void Access(int x,int v) {
    for(int y=0;x;x=fa[y=x]) {
        Splay(x),s[x]+=v,y?c[x]+=v:a[x]+=v;
        ll t=s[x]-s[ch[x][0]];
        /*
            s[x]=a[x]+s[ch[x][1]]+c[x];
            这里和s[ch[x][0]没有关系,但是可能已经算进了s[x],于是减去。
            (好像是这样的?感性理解一下[汗])
        */
        if(s[ch[x][1]]*2<=t+1) c[x]+=s[ch[x][1]],ch[x][1]=0;
        if(s[y]*2>t+1) c[x]-=s[y],ch[x][1]=y;
        ans-=dp[x],dp[x]=min(t-1,2ll*(t-max(s[ch[x][1]],a[x]))),ans+=dp[x];
        /*更新答案*/
    }
}

int main() {
    IN(n),IN(m);
    for(int i=1;i<=n;++i) IN(a[i]);
    for(int i=1,u,v;i<n;++i) IN(u),IN(v),add(u,v),add(v,u);
    dfs(1,0),printf("%lld\n",ans);
    while(m--) {
        int x,w;IN(x),IN(w);
        Access(x,w),printf("%lld\n",ans);
    }
    return 0;
}
/*代码还挺短的*/
最后修改:2019 年 08 月 29 日 04 : 17 PM