[hdu7012]Miserable Faith

本文主要是介绍[hdu7012]Miserable Faith，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

类似于[NOI2021]轻重边的逆过程，操作1即为对$u$​执行access（根为1），$dist(u,v)$​即为$u$​到$v$​的虚边数

对前者用LCT维护，并记录轻重边的切换，显然切换总量为$o(n\log n)$

换言之，问题即要支持：

1.修改一条边的边权（实边边权为0，虚边边权为1），共$o(n\log n)$​次

2.查询两点间的带权距离

3.查询一个点到子树内所有点的带权距离和

4.查询所有重链长度$l$的$\frac{l(l-1)}{2}$之和

关于询问2，将修改边权转换为子树修改和单点查询，并特判lca处即可

关于询问3，即子树内所有边权为1的边的子树大小之和，同样可以子树查询

关于询问4，在切换轻重边时维护即可（即splay的子树大小）

最终，总复杂度为$o(n\log^{2}n)$​，可以通过

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 100005
  4 #define ll long long
  5 #define L (k<<1)
  6 #define R (L+1)
  7 #define mid (l+r>>1)
  8 int E,t,n,m,p,x,y,head[N],dfn[N],sz[N],dep[N],fa[N][20];
  9 ll ans,f[2][N];
 10 struct Edge{
 11     int nex,to;
 12 }edge[N<<1];
 13 int lowbit(int k){
 14     return (k&(-k));
 15 }
 16 void update(int p,int k,int x){
 17     while (k<=n){
 18         f[p][k]+=x;
 19         k+=lowbit(k);
 20     }
 21 }
 22 ll query(int p,int k){
 23     ll ans=0;
 24     while (k){
 25         ans+=f[p][k];
 26         k-=lowbit(k);
 27     }
 28     return ans;
 29 }
 30 void update(int k,int p){
 31     update(0,dfn[k],p);
 32     update(0,dfn[k]+sz[k],-p);
 33     update(1,dfn[k],p*sz[k]);
 34 }
 35 int lca(int x,int y){
 36     if (dep[x]<dep[y])swap(x,y);
 37     for(int i=19;i>=0;i--)
 38         if (dep[fa[x][i]]>=dep[y])x=fa[x][i];
 39     if (x==y)return x;    
 40     for(int i=19;i>=0;i--)
 41         if (fa[x][i]!=fa[y][i]){
 42             x=fa[x][i];
 43             y=fa[y][i];
 44         }
 45     return fa[x][0];
 46 }
 47 namespace LCT{
 48     int fa[N],sz[N],ch[N][2];
 49     ll C(int k){
 50         return (ll)k*(k-1)/2;
 51     }
 52     void clear(){
 53         memset(fa,0,sizeof(fa));
 54         memset(ch,0,sizeof(ch));
 55         for(int i=1;i<=n;i++)sz[i]=1;
 56     }
 57     bool which(int k){
 58         return ch[fa[k]][1]==k;
 59     }
 60     bool check(int k){
 61         return ch[fa[k]][which(k)]!=k;
 62     }
 63     void up(int k){
 64         sz[k]=sz[ch[k][0]]+sz[ch[k][1]]+1;
 65     }
 66     void rotate(int k){
 67         int f=fa[k],g=fa[f],p=which(k);
 68         fa[k]=g;
 69         if (!check(f))ch[g][which(f)]=k;
 70         fa[ch[k][p^1]]=f,ch[f][p]=ch[k][p^1];
 71         fa[f]=k,ch[k][p^1]=f;
 72         up(f),up(k);
 73     } 
 74     void splay(int k){
 75         for(int i=fa[k];!check(k);i=fa[k]){
 76             if (!check(i)){
 77                 if (which(i)==which(k))rotate(i);
 78                 else rotate(k);
 79             }
 80             rotate(k);
 81         }
 82     }
 83     void get_min(int &k){
 84         while (ch[k][0])k=ch[k][0];
 85         splay(k);
 86     }
 87     void access(int k){
 88         int lst=0;
 89         while (k){
 90             splay(k),ans-=C(sz[k]);
 91             if (lst){
 92                 get_min(lst);
 93                 update(lst,-1);
 94             }
 95             swap(ch[k][1],lst);
 96             if (lst){
 97                 ans+=C(sz[lst]);
 98                 get_min(lst);
 99                 update(lst,1);
100             }
101             up(k),lst=k,k=fa[k];
102         }
103         ans+=C(sz[lst]);
104     }
105 };
106 void add(int x,int y){
107     edge[E]=Edge{head[x],y};
108     head[x]=E++;
109 }
110 void dfs(int k,int f,int s){
111     dfn[k]=++dfn[0];
112     sz[k]=1;
113     dep[k]=s;
114     fa[k][0]=LCT::fa[k]=f;
115     if (!f)fa[k][0]=k;
116     for(int i=1;i<20;i++)fa[k][i]=fa[fa[k][i-1]][i-1];
117     for(int i=head[k];i!=-1;i=edge[i].nex)
118         if (edge[i].to!=f){
119             dfs(edge[i].to,k,s+1);
120             sz[k]+=sz[edge[i].to];
121         }
122 }
123 int main(){
124     scanf("%d",&t);
125     while (t--){
126         scanf("%d%d",&n,&m);
127         E=ans=dfn[0]=0;
128         LCT::clear();
129         memset(head,-1,sizeof(head));
130         memset(f,0,sizeof(f));
131         for(int i=1;i<n;i++){
132             scanf("%d%d",&x,&y);
133             add(x,y);
134             add(y,x);
135         } 
136         dfs(1,0,0);
137         for(int i=2;i<=n;i++)update(i,1);
138         for(int i=1;i<=m;i++){
139             scanf("%d",&p);
140             if (p==1){
141                 scanf("%d%*d",&x);
142                 LCT::access(x);
143             }
144             if (p==2){
145                 scanf("%d%d",&x,&y);
146                 printf("%d\n",query(0,dfn[x])+query(0,dfn[y])-(query(0,dfn[lca(x,y)])<<1));
147             }
148             if (p==3){
149                 scanf("%d",&x);
150                 printf("%lld\n",query(1,dfn[x]+sz[x]-1)-query(1,dfn[x]));
151             }
152             if (p==4)printf("%lld\n",ans);
153         }
154     }
155     return 0;
156 } 

这篇关于[hdu7012]Miserable Faith的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！