正題

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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。