脚本宝典收集整理的这篇文章主要介绍了【CF1137F】Matches Are Not a Child's Play（LCT），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
题目链接
显然，最大点一定在删除序列中的最末端。因为除非只剩最后一个点，叶节点一定不止一个，也就肯定存在叶节点比最大点编号更小。
然后考虑次大点，找出它与最大点之间的树上路径，则这条路径上的点一定从次大点开始依次出现在删除序列的最末端。同样因为除非叶节点恰好为次大点和最大点，肯定存在叶节点比次大点编号更小；而删去次大点之后，剩下这条路径上所有点就会被依次删去。
以此类推，从大到小考虑每个点，如果它尚未确定，则它到之前已确定部分的路径在删除序列中会恰好出现在之前已确定部分的前面、尚未确定部分的最末端。
这种东西似乎难以实现。但我们反过来考虑，从小到大考虑每个点，将它到最大点的路径打通（打通指的是只保留这条路径上的边，而隐去这条路径上的点其他的连边）。因为较大点的路径会更后打通，所以最终以某个点为底端的连通链就是这个点到它之前已确定部分的路径。
而这个所谓的“打通”就是以最大点为根时 LCT 中的 Access 操作。
所以我们只要维护好这些连通链，将它们按底端编号排序，则一个点在删除序列中的排名就是它所在链之前所有连通链大小之和加上它在所在链中的排名。
这可以用一个以底端编号为下标的树状数组来维护。
考虑修改操作，被操作的点一定会变成最大点。
找出它与原最大点之间的路径，根据先前的结论它们将在最后被删除，应当形成一条新的连通链。
而其余的连通链在除去现最大点与原最大点之间的部分后并不会发生变化。
所以实际上只需要把根改为现最大点，然后打通原最大点到现最大点的路径即可。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 200000
using namespace std;
int n;
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
I void readc(char& x) {W(isspace(x=tc()));}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
int Tsz;struct TreeArray//树状数组
{
int a[2*N+5];I void A(RI x,CI v) {if(!~x) return;W(x<=Tsz) a[x]+=v,x+=x&-x;}
I int Q(RI x) {RI t=0;W(x) t+=a[x],x-=x&-x;return t;}
}T;
class LinkCutTree
{
private:
#define IR(x) (O[O[x].F].S[0]^x&&O[O[x].F].S[1]^x)
#define Wh(x) (O[O[x].F].S[1]==x)
#define Co(x,y,d) (O[O[x].F=y].S[d]=x)
#define PU(x) (O[x].Sz=O[O[x].S[0]].Sz+O[O[x].S[1]].Sz+1)
#define PD(x) (O[x].P&&(Ts(O[x].S[0],O[x].P),Ts(O[x].S[1],O[x].P),O[x].P=0),O[x].R&&(Re(O[x].S[0]),Re(O[x].S[1]),O[x].R=0))
#define Ts(x,v) (O[x].G=O[x].P=v)
#define Re(x) (x)&&(swap(O[x].S[0],O[x].S[1]),O[x].R^=1)
int St[N+5];struct node {int Sz,G,P,F,R,S[2];}O[N+5];
I void Ro(RI x) {RI f=O[x].F,p=O[f].F,d=Wh(x);!IR(f)&&(O[p].S[Wh(f)]=x),O[x].F=p,Co(O[x].S[d^1],f,d),Co(f,x,d^1),PU(f);}
I void S(RI x) {RI f=x,T=0;W(St[++T]=f,!IR(f)) f=O[f].F;W(T) PD(St[T]),--T;W(!IR(x)) f=O[x].F,!IR(f)&&(Ro(Wh(x)^Wh(f)?x:f),0),Ro(x);PU(x);}
I int FR(RI x) {Ac(x),S(x);W(O[x].S[0]) PD(x),x=O[x].S[0];return S(x),x;}
public:
I void Init() {O[0].G=-1;for(RI i=1;i<=n;++i) O[i].G=-1,O[i].Sz=1;}//初始化
I void Link(CI x,CI y) {MR(x),O[x].F=y;}I void MR(CI x) {Ac(x),S(x),Re(x);}
I int Q(CI x) {return S(x),T.Q(O[x].G-1)+O[O[x].S[1]].Sz+1;}//之前所有连通链大小之和+在所在链中的排名
I void Ac(RI x,CI tg=-1)//打通，标记为tg
{
RI y;for(y=0;x;x=O[y=x].F) S(x),T.A(O[x].G,-O[x].Sz),T.A(O[O[x].S[1]].G,O[O[x].S[1]].Sz),O[x].S[1]=y,PU(x);//打通，与右儿子断开
Ts(y,tg),T.A(tg,O[y].Sz);//将新的连通链标记为tg
}
}LCT;
int main()
{
RI Qt,i,x,y;for(read(n,Qt),Tsz=n+Qt,LCT.Init(),i=1;i^n;++i) read(x,y),LCT.Link(x,y);
for(LCT.MR(n),i=1;i^n;++i) LCT.Ac(i,i);//以最大点为根，从小到大将每个点到最大点路径打通
char op;RI rt=n,tt=n;W(Qt--)
{
if(readc(op),read(x),op=='u') {rt^x&&(LCT.MR(x),LCT.Ac(rt,tt),rt=x,++tt);continue;}//修改
op=='w'?writeln(LCT.Q(x)):(read(y),writeln(LCT.Q(x)<LCT.Q(y)?x:y));//询问，判断先后直接询问位置比大小
}return clear(),0;
}
以上是脚本宝典为你收集整理的【CF1137F】Matches Are Not a Child's Play（LCT）全部内容，希望文章能够帮你解决【CF1137F】Matches Are Not a Child's Play（LCT）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。