生活随笔
收集整理的這篇文章主要介紹了
洛谷P4219 大融合（LCT、虚子树）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
解析
本題需要用LCT維護子樹大小
然后我就不會了
然后我就用樹剖水過去了
又快又好寫，真香
現在詳細聊聊如何用LCT維護子樹信息
每個結點再定義一個新的變量記錄所有虛兒子的信息
然后…完了？
告別盲目pushup，我們來詳細聊聊在哪里需要更新虛兒子的信息
毋庸置疑，應該在虛兒子信息改變的時候（廢話）
那么什么時候發生改變呢？
access：虛實邊會交換狀態，需要更新虛子樹狀態link：增加了虛兒子，需要更新虛子樹狀態
沒了
splay、rotate、makeroot、findroot都是在一個splay里自己玩泥巴，顯然不會改變虛兒子的狀態
注意cut是減少了一個實兒子，也沒有改變虛兒子狀態
似乎還不太難對吧
所以，對于LCT的標記問題，我們要理性分析，相信科學
update:
紙上得來終覺淺，絕知此事要躬行
（翻譯：不要口胡）
qwq
不自己寫一遍是真的找不到坑點…
這里的link改變虛子樹狀態的時候，會連帶上面一串splay的信息都出問題！
而且由于其他地方默認的是原來的信息正確，因此這里即使后面splay或makeroot也于事無補
解決辦法是把y轉到根再更新其虛子樹信息
inline void link(int x
,int y
){makeroot(x
);access(y
);splay(y
);siz0
[y
]+=siz
[x
];f
[x
]=y
;pushup(y
);return;
}
代碼
然而懶得重寫，還是貼的我的樹剖
明天晨練可以寫遍這個
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=2e5+100;
const int mod
=1e9+7;
const double eps
=1e-9;
inline ll
read() {ll
x(0),f(1);char c
=getchar();while(!isdigit(c
)){if(c
=='-')f
=-1;c
=getchar();}while(isdigit(c
)){x
=(x
<<1)+(x
<<3)+c
-'0';c
=getchar();}return x
*f
;
}int n
,m
;
struct node{int to
,nxt
;
}p
[N
<<1];
int fi
[N
],cnt
;
inline void addline(int x
,int y
){p
[++cnt
]=(node
){y
,fi
[x
]};fi
[x
]=cnt
;return;
}
struct ope{int op
,x
,y
;
}q
[N
];
struct edge{int x
,y
;
}e
[N
];
int tot
,fa
[N
],num
[N
];
int find(int x
){return x
==fa
[x
]?x
:find(fa
[x
]);}
inline void merge(int x
,int y
){x
=find(x
);y
=find(y
);if(num
[x
]>num
[y
]) swap(x
,y
);e
[++tot
]=(edge
){x
,y
};fa
[x
]=y
;num
[y
]+=num
[x
];return;
}int dfn
[N
],pos
[N
],tim
,f
[N
],siz
[N
],hson
[N
],top
[N
];
int pl
[N
][19];
void dfs1(int x
,int fa
){f
[x
]=fa
;pl
[x
][0]=fa
;for(int k
=1;pl
[x
][k
-1];k
++) pl
[x
][k
]=pl
[pl
[x
][k
-1]][k
-1];siz
[x
]=1;for(int i
=fi
[x
];~i
;i
=p
[i
].nxt
){int to
=p
[i
].to
;if(to
==fa
) continue;dfs1(to
,x
);siz
[x
]+=siz
[to
];if(siz
[to
]>siz
[hson
[x
]]) hson
[x
]=to
;}return;
}
void dfs2(int x
,int tp
){top
[x
]=tp
;pos
[x
]=++tim
;dfn
[tim
]=x
;if(hson
[x
]) dfs2(hson
[x
],tp
);for(int i
=fi
[x
];~i
;i
=p
[i
].nxt
){int to
=p
[i
].to
;if(to
==f
[x
]||to
==hson
[x
]) continue;dfs2(to
,to
);}return;
}int val
[N
];
inline void add(int p
,int w
){for(;p
<=n
;p
+=p
&-p
) val
[p
]+=w
;return;
}
inline int ask(int p
){int res(0);for(;p
;p
-=p
&-p
) res
+=val
[p
];return res
;
}
void init(){for(int i
=1;i
<=n
;i
++){add(pos
[i
],siz
[i
]);add(pos
[i
]+1,-siz
[i
]);}return;
}void upd(int x
,int anc
,int w
){while(top
[x
]!=top
[anc
]){add(pos
[top
[x
]],w
);add(pos
[x
]+1,-w
);x
=f
[top
[x
]];}add(pos
[anc
],w
);add(pos
[x
]+1,-w
);return;
}ll ans
[N
];
int o
;
int main() {
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifmemset(fi
,-1,sizeof(fi
));cnt
=-1;n
=read();m
=read();for(int i
=1;i
<=n
;i
++) num
[i
]=1,fa
[i
]=i
;for(int i
=1;i
<=m
;i
++){char c
;int x
,y
;scanf(" %c",&c
);x
=read(),y
=read();q
[i
]=(ope
){c
=='A',x
,y
};if(c
=='A'){addline(x
,y
);addline(y
,x
);merge(x
,y
);}}for(int i
=1;i
<=n
;i
++){if(!siz
[i
]){dfs1(i
,0);dfs2(i
,i
);}}init();for(int i
=m
;i
>=1;i
--){if(q
[i
].op
){int x
=e
[tot
].x
,y
=e
[tot
].y
;--tot
;num
[y
]-=num
[x
];fa
[x
]=x
;x
=q
[i
].x
,y
=q
[i
].y
; if(f
[x
]==y
) swap(x
,y
);int w
=ask(pos
[y
]);int tp
=x
,oo
=find(x
);for(int k
=17;k
>=0;k
--){if(!pl
[tp
][k
]||find(pl
[tp
][k
])!=oo
) continue;tp
=pl
[tp
][k
];}upd(x
,tp
,-w
);}else{int x
=q
[i
].x
,y
=q
[i
].y
;if(f
[x
]==y
) swap(x
,y
);int sum
=num
[find(x
)],bot
=ask(pos
[y
]);ans
[++o
]=1ll*bot
*(sum
-bot
);}}while(o
) printf("%lld\n",ans
[o
--]);return 0;
}
總結
以上是生活随笔為你收集整理的洛谷P4219 大融合（LCT、虚子树）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
