5 条题解
-
2
12322132131231 (褚战) LV 10 @ 2023-07-14 17:20:51
#include <cctype> #include <cstdio> #include <cstring> #include <cassert> #include <algorithm> using namespace std; const int MAXSIZE=30000020; int bufpos; char buf[MAXSIZE]; void init(){ #ifdef LOCAL freopen("1985.txt","r",stdin); #endif buf[fread(buf,1,MAXSIZE,stdin)]='\0'; bufpos=0; } int readint(){ bool isneg; int val=0; for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++); bufpos+=(isneg=(buf[bufpos]=='-'))?1:0; for(;isdigit(buf[bufpos]);bufpos++) val=val*10+buf[bufpos]-'0'; return isneg?-val:val; } char readchar(){ for(;isspace(buf[bufpos]);bufpos++); return buf[bufpos++]; } struct edge{ int from,to,next; }; struct graph{ int n,m; edge e[400001]; int first[100001]; int fa[100001]; int par[100001][21]; int dep[100001]; int dist[100001]; int maxi; int sz[100001]; int val[100001]; void init(int n,int *a){ this->n=n; maxi=32-__builtin_clz(n); m=0; memset(first,-1,sizeof(first)); memcpy(val,a,sizeof(val)); for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1,dep[i]=1,dist[i]=val[i]; } void addedge(int from,int to){ e[++m]=(edge){from,to,first[from]}; first[from]=m; } int getf(int x){ return fa[x]==x?x:fa[x]=getf(fa[x]); } void dfs(int u,int pa){ for(int i=1;i<=maxi;i++) par[u][i]=par[par[u][i-1]][i-1]; for(int i=first[u];i!=-1;i=e[i].next){ int v=e[i].to; if (v!=pa){ par[v][0]=u; dep[v]=dep[u]+1; dist[v]=dist[u]+val[v]; dfs(v,u); } } } int lca(int u,int v){ if (dep[u]<dep[v]) swap(u,v); int t=dep[u]-dep[v]; for(int i=0;i<=maxi;i++){ if (t&(1<<i)) u=par[u][i]; } if (u==v) return u; for(int i=maxi;i>=0;i--){ if (par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i]; } return par[u][0]; } void link(int u,int v){ int x=getf(u),y=getf(v); if (sz[x]>sz[y]) swap(u,v),swap(x,y); fa[x]=y; sz[y]+=sz[x]; sz[x]=0; addedge(u,v); addedge(v,u); par[u][0]=v; dep[u]=dep[v]+1; dist[u]=dist[v]+val[u]; dfs(u,v); } int query(int u,int v){ int lc=lca(u,v); return dist[u]+dist[v]-dist[lc]*2+val[lc]; } }g; int a[100001]; int main(){ init(); int n=readint(); for(int i=1;i<=n;i++) a[i]=readint(); g.init(n,a); for(int i=1;i<=n;i++){ int u=readint(),v=readint(); if (!u) continue; g.link(u,v); } int m=readint(),lastans=0; for(int i=1;i<=m;i++){ char c=readchar(); int u=readint()^lastans,v=readint()^lastans; if (c=='Q') printf("%d\n",lastans=g.query(u,v)); else g.link(u,v); } } -
0
启发式合并+倍增LCA即可。每次合并时将所在的树大小小的（设为\(u\)）合并到大的（设为\(v\)），将\(u\)的父亲设为\(v\)，将\(u\)所在的整棵树以\(u\)为根重建。重建时维护倍增数组和\(dist\)数组（\(dist[u]\)表示\(u\)到\(u\)所在的树的根的距离）。查询时设\(LCA(u,v)=lc\)，答案为
\(dist[u]+dist[v]-2*dist[lc]+val[lc]\)（\(val[lc]\)表示\(lc\)的权值）。这样，每个点所在的树的大小在这个点被重建时至少会翻倍，
因此每个点最多被重建 \(O(\log n)\) 次而每次重建一个点的复杂度为 \(O(\log n)\) 总共有n个点，因此最终的时间复杂度为
\(O(n \log^2 n)\)C++ Code
#include <cctype> #include <cstdio> #include <cstring> #include <cassert> #include <algorithm> using namespace std; const int MAXSIZE=30000020; int bufpos; char buf[MAXSIZE]; void init(){ #ifdef LOCAL freopen("1985.txt","r",stdin); #endif buf[fread(buf,1,MAXSIZE,stdin)]='\0'; bufpos=0; } int readint(){ bool isneg; int val=0; for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++); bufpos+=(isneg=(buf[bufpos]=='-'))?1:0; for(;isdigit(buf[bufpos]);bufpos++) val=val*10+buf[bufpos]-'0'; return isneg?-val:val; } char readchar(){ for(;isspace(buf[bufpos]);bufpos++); return buf[bufpos++]; } struct edge{ int from,to,next; }; struct graph{ int n,m; edge e[400001]; int first[100001]; int fa[100001]; int par[100001][21]; int dep[100001]; int dist[100001]; int maxi; int sz[100001]; int val[100001]; void init(int n,int *a){ this->n=n; maxi=32-__builtin_clz(n); m=0; memset(first,-1,sizeof(first)); memcpy(val,a,sizeof(val)); for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1,dep[i]=1,dist[i]=val[i]; } void addedge(int from,int to){ e[++m]=(edge){from,to,first[from]}; first[from]=m; } int getf(int x){ return fa[x]==x?x:fa[x]=getf(fa[x]); } void dfs(int u,int pa){ for(int i=1;i<=maxi;i++) par[u][i]=par[par[u][i-1]][i-1]; for(int i=first[u];i!=-1;i=e[i].next){ int v=e[i].to; if (v!=pa){ par[v][0]=u; dep[v]=dep[u]+1; dist[v]=dist[u]+val[v]; dfs(v,u); } } } int lca(int u,int v){ if (dep[u]<dep[v]) swap(u,v); int t=dep[u]-dep[v]; for(int i=0;i<=maxi;i++){ if (t&(1<<i)) u=par[u][i]; } if (u==v) return u; for(int i=maxi;i>=0;i--){ if (par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i]; } return par[u][0]; } void link(int u,int v){ int x=getf(u),y=getf(v); if (sz[x]>sz[y]) swap(u,v),swap(x,y); fa[x]=y; sz[y]+=sz[x]; sz[x]=0; addedge(u,v); addedge(v,u); par[u][0]=v; dep[u]=dep[v]+1; dist[u]=dist[v]+val[u]; dfs(u,v); } int query(int u,int v){ int lc=lca(u,v); return dist[u]+dist[v]-dist[lc]*2+val[lc]; } }g; int a[100001]; int main(){ init(); int n=readint(); for(int i=1;i<=n;i++) a[i]=readint(); g.init(n,a); for(int i=1;i<=n;i++){ int u=readint(),v=readint(); if (!u) continue; g.link(u,v); } int m=readint(),lastans=0; for(int i=1;i<=m;i++){ char c=readchar(); int u=readint()^lastans,v=readint()^lastans; if (c=='Q') printf("%d\n",lastans=g.query(u,v)); else g.link(u,v); } }
12322132131231 (褚战)
LV 10
@ 2023-07-14 17:20:51
- 1
