自动搬运

查看原文

来自洛谷，原作者为

	Kelin 这个家伙太菜，没什么可以留下的

搬运于2025-08-24 21:59:08，当前版本为作者最后更新于2018-03-28 10:05:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给出一棵树,给定每一个点的$access$次数,计算轻重链切换次数的最大值,带修改.

题解

先考虑不带修改怎么做

可以发现一个点$u$,只有$u$子树里的点进行$access$才会影响$u$的答案,并且每个点都是独立的,可以分开计算

假设$u$的子树发生了两次$access$,那么当且仅当这两次$access$的点来自$u$的两个不同的儿子的子树,答案才会$+1$

设$A_0=a_u$,$A_i=[u$的第$i$个儿子子树$access$次数之和$],m=|Son_u|$

既然当且仅当两次$access$来自不同子树会使得答案$+1$

要使得答案最大,就是尽量让所有相邻发生的$access$都来自不同子树

转化一下也就是有$[0,m]$种颜色,每种颜色有$A_i$个,最大化相邻的颜色不同次数

设$t=\sum_{i=0}^mA_i,h=\max_{i=0}^m\{A_i\}$

那么答案就是$\min\{t-1,2\times(t-h)\}$

把同类型的数挪到一边就是当$2\times h\ge t+1$时,答案是$2(t-h)$,否则是$t-1$

这里举个例子说明一下答案为啥是那个

第一种情况

颜色$A\times3,B\times4,C\times5$

一组可行解是$CACBCACBCBAB$

答案是$11=12-1$

第二种情况

颜色$A\times2,B\times3,C\times7$

一组可行解是$CACBCACBCBCC$

答案是$10=2\times(12-7)$

至于你说严格的证明我可以跟你说我最多只能通过举例子理解了吗,当然你可以问数学好的$dalao$吧

这样我们就可以在$O(n)$的时间内$dfs$一下这棵树就可以得到答案了$(ps:$记得开$long\ long)$

考虑待修改怎么做

我们可以根据这个$[2\times h\ge t+1]$的"分界线"去想一想怎么维护答案

令$f_i$表示$i$的子树$access$的总次数,如果$2f_i\ge f_{fa_i}+1$那么连实边$(i,fa_i)$,其他的都是虚边

考虑到如果把$i$子树里的点$j$的权值加上$w$,他只会影响$j$到根路径上的点的答案和虚实边关系

因为$2(f_i+w)\ge(f_{fa_i}+w)+1$,所以实边还是实边,并且答案不会变化$(\Delta=2[(f_{fa_i}+w)-(f_i+w)]-2(f_{fa_i}-f_i)=0)$

所以我们只需要找到路径上的虚边进行修改就好了

并且可以知道一条路径上虚边的数量$\le\log\sum a$(证明和树剖的证明一样,有一个"重儿子")

所以我们可以找到路径上所有虚边,然后暴力修改就好了

至于怎么找到路径上的虚边,可以用树剖$+$在线段树/树状数组上二分找到

当然还可以写$LCT$,因为这里的的操作其实就和$access$差不多,只是不一定会把所有边都变成实边,所以特判一下就好了,然后$ans+=$这个点更新后的答案$-$更新前的答案就好了

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=4e5+5;
typedef int arr[N];
typedef long long ll;
struct eg{int nx,to;}e[N*2];
int n,m,ce,fi[N];ll ans;
struct LCT{
    int fa[N],ch[N][2];ll s[N],val[N],vs[N];
    #define lc(u) (ch[u][0])
    #define rc(u) (ch[u][1])
    inline bool gf(int u){return rc(fa[u])==u;}
    inline bool ir(int u){return lc(fa[u])^u&&rc(fa[u])^u;}
    inline void up(int u){s[u]=s[lc(u)]+s[rc(u)]+val[u]+vs[u];}
    inline void rot(int u){
        int p=fa[u],k=gf(u);
        if(!ir(p))ch[fa[p]][gf(p)]=u;
        if(ch[u][!k])fa[ch[u][!k]]=p;
        ch[p][k]=ch[u][!k],ch[u][!k]=p;
        fa[u]=fa[p],fa[p]=u,up(p);
    }
    void splay(int u){
        for(int f=fa[u];!ir(u);rot(u),f=fa[u])
            if(!ir(f))rot(gf(f)==gf(u)?f:u);
        up(u);
    }
    inline ll calc(int u,ll t,ll h){return rc(u)?(t-h)*2:(val[u]*2>t?(t-val[u])*2:t-1);}
    inline void mdy(int u,int w){
        splay(u);int v;
        ll t=s[u]-s[lc(u)],h=s[rc(u)];
        ans-=calc(u,t,h);s[u]+=w,val[u]+=w,t+=w;
        if(h*2<t+1)vs[u]+=h,rc(u)=0;
        ans+=calc(u,t,h);up(u);
        //access
        for(u=fa[v=u];u;u=fa[v=u]){
            splay(u);t=s[u]-s[lc(u)],h=s[rc(u)];
            ans-=calc(u,t,h);s[u]+=w,vs[u]+=w,t+=w;
            if(h*2<t+1)vs[u]+=h,rc(u)=0,h=0;
            if(s[v]*2>t)vs[u]-=s[v],rc(u)=v,h=s[v];
            ans+=calc(u,t,h);up(u);
        }
    }
    void dfs(int u){
        s[u]=val[u];int p=0;ll mx=val[u];
        go(u)if(v^fa[u]){
            fa[v]=u,dfs(v),s[u]+=s[v];
            if(s[v]>mx)mx=s[p=v];
        }
        ans+=min(s[u]-1,(s[u]-mx)*2);
        if(mx*2>=s[u]+1)rc(u)=p;
        vs[u]=s[u]-val[u]-s[rc(u)];
    }
}t;
inline void add(int u,int v){e[++ce]={fi[u],v},fi[u]=ce;}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n),sd(m);int u,v;
    fp(i,1,n)sd(t.val[i]);
    fp(i,2,n)sd(u),sd(v),add(u,v),add(v,u);
    t.dfs(1);we(ans);
    while(m--){
        sd(u),sd(v);
        t.mdy(u,v);
        we(ans);
    }
return Ot(),0;
}

那个$calc(u,t,h)$或许这么写会好理解一些$?$

inline ll calc(int u,ll t,ll h){
	if(rc(u))return (t-h)*2;
	else if(val[u]>=t+1)return (t-val[u])*2;
	else return t-1
}