[cf1137F]Matches Are Not a Child's Pla

显然compare操作可以通过两次when操作实现，以下仅考虑前两种操作

为了方便，将优先级最高的节点作为根，显然根最后才会被删除

接下来，不断找到剩下的节点中（包括根）优先级最高的节点，将其到其所在树根的所有节点从下到上依次加入到序列的开头并删除，不难发现最终得到的序列即为燃烧的顺序

将每一次删除的链上的边称为实边，其余边称为虚边，实际上就构成了一个类似于LCT的结构

一次$v$的修改操作对该LCT的影响，简单分析后不难发现即为将$v$换为根

考虑节点$v$的答案，即分为两部分：

1.定义其中一条实链（一个Splay）的优先级为其中优先级最大的节点（链尾），所有实链中优先级比$v$所在实链小的长度（指节点个数）和

2.$v$所在实链中比$v$浅的点个数（包括$v$自身）

前者可以在LCT修改的过程中再维护一个树状数组（以优先级为下标，长度为权值），后者直接在LCT中查询该节点（将其Splay到根）即可，将两者求和即为答案

时间复杂度为$o(n\log n)$，可以通过

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 200005

  4 struct Edge{

  5     int nex,to;

  6 }edge[N<<1];

  7 int E,n,m,x,y,head[N],f[N<<1],st[N],fa[N],val[N],sz[N],rev[N],ch[N][2];

  8 char s[11];

  9 int lowbit(int k){

 10     return (k&(-k));

 11 }

 12 void update(int k,int x){

 13     while (k<=n+m){

 14         f[k]+=x;

 15         k+=lowbit(k);

 16     }

 17 }

 18 int query(int k){

 19     int ans=0;

 20     while (k){

 21         ans+=f[k];

 22         k-=lowbit(k);

 23     }

 24     return ans;

 25 }

 26 int which(int k){

 27     return ch[fa[k]][1]==k;

 28 }

 29 int check(int k){//返回1当且仅当不是根节点

 30     return ch[fa[k]][which(k)]==k;

 31 }

 32 void upd(int k){

 33     rev[k]^=1;

 34     swap(ch[k][0],ch[k][1]);

 35 }

 36 void up(int k){

 37     sz[k]=sz[ch[k][0]]+sz[ch[k][1]]+1;

 38 }

 39 void down(int k){

 40     if (ch[k][0])val[ch[k][0]]=val[k];

 41     if (ch[k][1])val[ch[k][1]]=val[k];

 42     if (rev[k]){

 43         upd(ch[k][0]);

 44         upd(ch[k][1]);

 45         rev[k]=0;

 46     }

 47 }

 48 void rotate(int k){

 49     int f=fa[k],g=fa[f],p=which(k);

 50     fa[k]=g;

 51     if (check(f))ch[g][which(f)]=k;

 52     fa[ch[k][p^1]]=f,ch[f][p]=ch[k][p^1];

 53     fa[f]=k,ch[k][p^1]=f;

 54     up(f),up(k);

 55 }

 56 void splay(int k){

 57     for(int i=k;;i=fa[i]){

 58         st[++st[0]]=i;

 59         if (!check(i))break;

 60     }

 61     while (st[0])down(st[st[0]--]);

 62     for(int i=fa[k];check(k);i=fa[k]){

 63         if (check(i)){

 64             if (which(k)==which(i))rotate(i);

 65             else rotate(k);

 66         }

 67         rotate(k);

 68     }

 69 }

 70 void access(int k){

 71     int lst=0;

 72     while (k){

 73         splay(k);

 74         update(val[k],sz[ch[k][1]]-sz[k]);

 75         ch[k][1]=lst,up(k);

 76         lst=k,k=fa[k];

 77     }

 78 }

 79 void make_root(int k){

 80     access(k);

 81     splay(k);

 82     upd(k);

 83 }

 84 void add(int x,int y){

 85     edge[E].nex=head[x];

 86     edge[E].to=y;

 87     head[x]=E++;

 88 }

 89 void dfs(int k,int f){

 90     fa[k]=f,val[k]=k;

 91     for(int i=head[k];i!=-1;i=edge[i].nex)

 92         if (edge[i].to!=f){

 93             dfs(edge[i].to,k);

 94             val[k]=max(val[k],val[edge[i].to]);

 95         }

 96     update(val[k],1);

 97     if (val[k]==k){

 98         sz[k]=1;

 99         return;

100     }

101     for(int i=head[k];i!=-1;i=edge[i].nex)

102         if ((edge[i].to!=f)&&(val[k]==val[edge[i].to])){

103             sz[k]=sz[edge[i].to]+1;

104             ch[k][1]=edge[i].to;

105             return;

106         }

107 }

108 void Update(int k){

109     make_root(k);

110     val[k]=++val[0];

111     update(val[k],sz[k]);

112 }

113 int Query(int k){

114     splay(k);

115     return query(val[k])-sz[ch[k][0]];

116 }

117 int main(){

118     scanf("%d%d",&n,&m);

119     memset(head,-1,sizeof(head));

120     for(int i=1;i<n;i++){

121         scanf("%d%d",&x,&y);

122         add(x,y),add(y,x);

123     }

124     dfs(n,0);

125     val[0]=n;

126     for(int i=1;i<=m;i++){

127         scanf("%s%d",s,&x);

128         if (s[0]=='u')Update(x);

129         if (s[0]=='w')printf("%d\n",Query(x));

130         if (s[0]=='c'){

131             scanf("%d",&y);

132             if (Query(x)<Query(y))printf("%d\n",x);

133             else printf("%d\n",y);

134         }

135     }

136     return 0;

137 }

巴特西

[cf1137F]Matches Are Not a Child's Pla

最新文章

热门文章