【LCT】历史（P4338）

本文主要是介绍【LCT】历史（P4338），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

P4338

---

题目大意

有一棵树，告诉你每个点access的次数（带修改），问实链切换的最多次数

---

解题思路

先考虑离线的做法：

对于点 x，其不同儿子的子树access会使实链切换（对于点 x access 同理），每次都让不同儿子的子树 access，显然可以让答案最大化

但答案不一定是 $s{z}_x-1$（最后无法切换），因为如果存在一个儿子 y 满足 $s{z}_y>s{z}_x-s{z}_y$，即该子树大小大于其他子树大小之和，那么不存在操作使得 y 中的每次access都被切换掉

所以当 $s{z}_y\times 2\ge s{z}_x+1$ 时答案为 $(s{z}_x-s{z}_y)\times 2$（最多切换这么多次不同的）， 否则为 $s{z}_x-1$

---

然后再考虑在线的做法：

考虑用LCT维护，实边连接满足 $s{z}_y\times 2\ge s{z}_x+1$ 的儿子（不存在则不连）

每次修改可能会修改当前点到根节点的实链，那么只需考虑对该段的影响

对于原来是实边的，显然加了之后仍然满足，不影响，对于原来是虚边的，先减去原来的贡献，然后再考虑连边计算贡献

每经过一次虚边，那么其他儿子的 sz 就必定大于 当前点的 sz，那么sz至少会变大一倍，所以最多经过 log 条虚边

时间复杂度 $O(nlogn)$

---

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define N 400400
ll n,m,x,y,tot,ans,top,a[N],h[N],d[N];
struct rec
{ll to,nx;
}e[N<<1];
void add(ll x,ll y)
{e[++tot].to=y;e[tot].nx=h[x];h[x]=tot;return;
}
struct LCT
{#define ls son[x][0]#define rs son[x][1]ll v[N],ss[N],s[N],fa[N],son[N][2];bool NR(ll x){return fa[x]&&(son[fa[x]][0]==x||son[fa[x]][1]==x);}bool IRS(ll x){return son[fa[x]][1]==x;}void push_up(ll x){s[x]=s[ls]+s[rs]+ss[x]+v[x];return;}void rotate(ll x){ll y=fa[x],z=fa[y],k=IRS(x),g=son[x][!k];if(NR(y))son[z][IRS(y)]=x;if(g)fa[g]=y;fa[x]=z;fa[y]=x;son[x][!k]=y;son[y][k]=g;push_up(y);return;}void Splay(ll x){while(NR(x)){if(NR(fa[x])){if(IRS(x)==IRS(fa[x]))rotate(fa[x]);else rotate(x);}rotate(x);}push_up(x);return;}ll get(ll x){if(rs)return (v[x]+ss[x])*2;else if(v[x]*2>=(s[x]-s[ls])+1)return ss[x]*2;else return (s[x]-s[ls])-1;}void access(ll x,ll z){Splay(x);ans-=get(x);//减去原有贡献v[x]+=z;s[x]+=z;if(rs&&s[rs]*2<s[x]-s[ls]+1){//断去原来的边ss[x]+=s[rs];rs=0;}ans+=get(x);ll y=x;x=fa[x];for(;x;x=fa[y=x]){Splay(x);ans-=get(x);ss[x]+=z;s[x]+=z;if(rs&&s[rs]*2<s[x]-s[ls]+1){ss[x]+=s[rs];rs=0;}if(s[y]*2>=s[x]-s[ls]+1){//连接新的实边rs=y;ss[x]-=s[rs];}ans+=get(x);}return;}
}T;
void dfs(ll x)//初始连边
{ll hs=0;T.v[x]=a[x];for(ll i=h[x];i;i=e[i].nx){ll y=e[i].to;if(y==T.fa[x])continue;T.fa[y]=x;dfs(y);T.ss[x]+=T.s[y];if(T.s[y]>T.s[hs])hs=y;}T.s[x]=T.v[x]+T.ss[x];if(T.s[hs]*2>=T.s[x]+1){T.son[x][1]=hs;T.ss[x]-=T.s[hs];ans+=(T.v[x]+T.ss[x])*2;}else if(T.v[x]*2>=T.s[x]+1){ans+=T.ss[x]*2;}else ans+=T.s[x]-1;return;
}
int main()
{scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;++i)scanf("%lld",&a[i]);for(ll i=1;i<n;++i){scanf("%lld%lld",&x,&y);add(x,y);add(y,x);}dfs(1);printf("%lld\n",ans);while(m--){scanf("%lld%lld",&x,&y);T.access(x,y);printf("%lld\n",ans);}return 0;
}

这篇关于【LCT】历史（P4338）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---