• 周一. 5月 27th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7012]Miserable Faith

admin

11月 28, 2021

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

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

换言之,问题即要支持:

1.修改一条边的边权(实边边权为0,虚边边权为1),共$o(nlog n)$​次

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

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

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

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

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

关于询问4,在切换轻重边时维护即可(即splay的子树大小)

最终,总复杂度为$o(nlog^{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
",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
",query(1,dfn[x]+sz[x]-1)-query(1,dfn[x]));
151             }
152             if (p==4)printf("%lld
",ans);
153         }
154     }
155     return 0;
156 } 

View Code

《[hdu7012]Miserable Faith》有5个想法
  1. Hi! Do you know if they make any plugins to help with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good success.
    If you know of any please share. Thank you! You can read similar art here:
    Ecommerce

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注