吉老师天下第一!
感觉这个题大概能算我见过的最神仙的数据结构题?
首先考虑把答案拆到每一个点上, 即去计算每一个点会被贡献多少次.
显然, 对于一个点来说, 只有它子树内的崛起可能会在它这里产生贡献.
具体一点, 如果它子树内部连续崛起的两个点属于两个不同的儿子, 那么贡献 + 1.
那么就转化为这样找一个问题.
有 n 个物品, 按照颜色划分为 k 种, 每种有 a1,a2,a3..ak 个.
把这些物品摆成一排, 两个相邻的物品如果颜色不同, 那么贡献 + 1, 求最大贡献.
结论:
设 p 为 a 数组最大值, 则 ans=min(n-1,2*(n-p))
证明:
首先上界显然是 n-1.
如果最大值超过一半的话, 那么最大值一定会发生 "同色相邻" 的情况, 只能产生 n-p 对贡献.
如果最大值不超过一半的话, 那么就先把最大值排成一排, 然后再找出次大值, 依次插入每一个间隔中, 递归着做下去, 就可以达到上界 n-1.
有了这个结论, 就可以通过简单树形 dp 解决没有修改的情况.
如果带修改怎么做?
分析一下那个式子, 考虑答案取到 n-1 的条件 ----------->2k<n+1, 即 2k<=n.
我们考虑进行一波轻重链剖分,
对于 2k<=n 的边连轻边, 对于 2k>n 的边连重边.
这样可以保证任何一个点到根的轻边数量不会超过 logn.
然后用 LCT 来大力维护这个东西.
用一个数组, 存一下当前每个点在 min(n-1,2(n-k)) 具体是怎么被贡献的.
修改的时候, 对于重链, 由于取到的答案是 2(n-k), 同时变大相同的量, 无需修改.
对于轻边, 判断一下修改后是否大于一半, 如果大于一半就把轻边改为重边.
同理, 如果父亲加上一个权值后是的原本的重儿子变为轻儿子, 也要修改一下.
- #include<bits/stdc++.h>
- #define N 440000
- #define eps 1e-7
- #define inf 1e9+7
- #define db double
- #define ll long long
- #define ldb long double
- using namespace std;
- inline ll read()
- {
- char ch=0;
- ll x=0,flag=1;
- while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
- while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
- return x*flag;
- }
- #define lson son[x][0]
- #define rson son[x][1]
- ll f[N],v[N],sw[N],sv[N],flag[N],son[N][2];
- bool get(ll x){return son[f[x]][1]==x;}
- bool isrt(ll x){return x!=son[f[x]][0]&&x!=son[f[x]][1];}
- void pushup(ll x){sw[x]=sw[lson]+sw[rson]+sv[x]+v[x];}
- void rotate(ll x)
- {
- ll y=f[x],z=f[y],tx=get(x),ty=get(y),p=son[x][!tx];
- if(!isrt(y))son[z][ty]=x;son[x][!tx]=y;son[y][tx]=p;
- if(p)f[p]=y;f[x]=z;f[y]=x;pushup(y);pushup(x);
- }
- void splay(ll x)
- {
- while(!isrt(x))
- {
- ll y=f[x];
- if(!isrt(y))rotate(get(x)==get(y)?x:y);
- rotate(x);
- }
- }
- struct edge{ll to,nxt;}e[N*2];
- ll num,head[N];
- inline void add(ll x,ll y){e[++num]={y,head[x]};head[x]=num;}
- ll n,m,ans=0;
- void dfs(ll x,ll fa)
- {
- ll k=x,mx=v[x],tot=v[x];
- for(ll i=head[x];i!=-1;i=e[i].nxt)
- {
- ll to=e[i].to;
- if(to==fa)continue;
- dfs(to,x);
- f[to]=x;tot+=sw[to];
- if(mx<sw[to])k=to,mx=sw[to];
- }
- sv[x]=tot-v[x];sw[x]=tot;
- if(k!=x&&2*mx>tot){flag[x]=0;rson=k;sv[x]-=mx;ans+=2*(tot-mx);return;}
- if(k==x&&2*mx>tot){flag[x]=1;ans+=2*(tot-v[x]);return;}
- if(2*mx<=tot){flag[x]=2;ans+=tot-1;return;}
- }
- int main()
- {
- n=read();m=read();
- for(ll i=1;i<=n;i++)v[i]=read();
- num=-1;memset(head,-1,sizeof(head));
- for(ll i=2;i<=n;i++){ll x=read(),y=read();add(x,y);add(y,x);}
- dfs(1,1);printf("%lld\n",ans);
- for(ll i=1;i<=m;i++)
- {
- ll x=read(),k=read();
- for(ll y=0;x;y=x,x=f[x])
- {
- splay(x);
- ll s=sw[x]-sw[lson];
- if(flag[x]==0)ans-=2*(s-sw[rson]);// 某个子树大于等于 n/2
- if(flag[x]==1)ans-=2*(s-v[x]);// 自己大于等于 n/2
- if(flag[x]==2)ans-=s-1;// 都小于 n/2
- s+=k;sw[x]+=k;if(!y)v[x]+=k;else sv[x]+=k;
- if(2*sw[y]>s)sv[x]+=sw[rson],rson=y,sv[x]-=sw[rson];
- if(2*sw[rson]>s)flag[x]=0,ans+=2*(s-sw[rson]);// 某个子树大于等于 n/2
- else
- {
- sv[x]+=sw[rson];rson=0;
- if(2*v[x]>s)flag[x]=1,ans+=2*(s-v[x]);// 自己大于等于 n/2
- else flag[x]=2,ans+=s-1;// 都小于 n/2
- }
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
[ZJOI2018] 历史
来源: http://www.bubuko.com/infodetail-3043012.html