轻重链剖分+启发式合并专题

Codeforces-741D(Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths)

一棵根为1 的树，每条边上有一个字符（a-v共22种）。 一条简单路径被称为Dokhtar-kosh当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的Dokhtar-kosh路径的长度。给你n个点构成的一棵树，树里面的每一条边有一个权值，求出每个子树里面能通过重排构成回文串的最大路径长度.

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=2*N;
int h[N],e[M],ne[M],w[M],idx;
int n,id[N],L[N],R[N],o,son[N],sz[N],dep[N],dfn[N];
int d[N],f[1<<23],ans[N],flag;
void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int fa=0){dep[u]=dep[fa]+1;dfn[u]=++o,id[o]=u;sz[u]=1;L[u]=o;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa)continue;d[j]=d[u]^w[i];//d[j]表示从根节点到j的结点状态dfs1(j,u);sz[u]+=sz[j];if(sz[son[u]]<sz[j])son[u]=j;}R[u]=o;
}
void upd(int u){if(f[d[u]])ans[u]=max(ans[u],f[d[u]]-dep[u]);for(int i=0;i<22;i++){int x=d[u]^(1<<i);if(f[x])ans[u]=max(ans[u],f[x]-dep[u]);}
}
void upd2(int j,int u){if(f[d[j]])ans[u]=max(ans[u],f[d[j]]+(dep[j]-dep[u])-dep[u]);for(int i=0;i<22;i++){int x=d[j]^(1<<i);if(f[x])ans[u]=max(ans[u],f[x]+(dep[j]-dep[u])-dep[u]);}
}
void cal(int u,int fa){upd(u);//先更新贡献f[d[u]]=max(f[d[u]],dep[u]);//把我自己插进去for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==son[u]||j==fa)continue;for(int x=L[j];x<=R[j];x++)upd2(id[x],u);//计算子树所有节点和我构成的贡献for(int x=L[j];x<=R[j];x++)f[d[id[x]]]=max(f[d[id[x]]],dep[id[x]]);//插入这颗子树的贡献}
}
void dfs(int u,int fa=0,int keep=0){for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa||j==son[u])continue;//先枚举轻儿子，不保留dfs(j,u,0);ans[u]=max(ans[u],ans[j]);}if(son[u]){//再计算重儿子，保留答案int j=son[u];dfs(j,u,1);ans[u]=max(ans[u],ans[j]);flag=j;}cal(u,fa);//计算跟u节点相关的答案flag=0;if(!keep)for(int i=L[u];i<=R[u];i++)f[d[id[i]]]=0;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;memset(h,-1,sizeof h);char c;for(int i=2,j;i<=n;i++)cin>>j>>c,add(j,i,1<<(c-'a')),add(i,j,1<<(c-'a'));dfs1(1);dfs(1);for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

---

阔力梯的树

用启发式合并写

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,sz[N];
long long f[N];
vector<int>g[N],son[N];
set<int>S[N];
void dfs(int u){sz[u]=1;S[u].insert(u);for(auto j:g[u]){dfs(j);if(sz[u]<sz[j])swap(sz[u],sz[j]),swap(S[u],S[j]),f[u]=f[j];//这里swap有一个坑点，f[j]是你最后要用的，已经记录好了的不要乱动，u用了j的set直接从f[j]就好了for(auto x:S[j]){auto it=S[u].lower_bound(x);if(it==S[u].begin())f[u]+=(x-*it)*(x-*it);else if(it==S[u].end())it--,f[u]+=(x-*it)*(x-*it);else{int r=*it;it--;int l=*it;f[u]-=(r-l)*(r-l);f[u]+=(x-l)*(x-l)+(x-r)*(x-r);}S[u].insert(x);}sz[u]+=sz[j];}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=2;i<=n;i++){int fa;cin>>fa;g[fa].push_back(i);}dfs(1);for(int i=1;i<=n;i++)cout<<f[i]<<'\n';
}

---

用树链剖分写

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,h[N],ne[N],e[N],idx;
int sz[N],id[N],L[N],R[N],o,son[N],ans[N];
set<int>S;
int f;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dsu(int u){sz[u]=1;L[u]=++o,id[o]=u;for(int i=h[u];~i;i=ne[i]){int j=e[i];dsu(j);if(sz[j]>sz[son[u]])son[u]=j;sz[u]+=sz[j];}R[u]=o;
}
void ins(int x){if(S.empty()){S.insert(x);return;}auto it=S.lower_bound(x);if(it==S.begin())f+=(x-*it)*(x-*it);else if(it==S.end())it--,f+=(x-*it)*(x-*it);else{int r=*it;it--;int l=*it;f-=(r-l)*(r-l);f+=(r-x)*(r-x)+(x-l)*(x-l);}S.insert(x);
}
void dfs(int u,int keep=0){for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==son[u])continue;dfs(j,0);}if(son[u])dfs(son[u],1);for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==son[u])continue;for(int k=L[j];k<=R[j];k++)ins(id[k]);}ins(u);ans[u]=f;if(!keep)f=0,S.clear();
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;memset(h,-1,sizeof h);for(int i=2;i<=n;i++){int fa;cin>>fa;add(fa,i);}dsu(1);dfs(1);for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}

---

F. Strange Memory

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=2e5+10,M=1e6+5e5;
int n,h[N],e[N],ne[N],idx,a[N];
int L[N],R[N],id[N],o,sz[N],son[N];
int f[2][20][M];
long long ans;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dsu(int u,int fa=0){sz[u]=1;L[u]=++o;id[o]=u;for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa)continue;dsu(j,u);if(sz[j]>sz[son[u]])son[u]=j;sz[u]+=sz[j];}R[u]=o;
}
void ins(int u,int k=1){for(int i=0;i<20;i++){int x=u>>i&1;f[x][i][a[u]]+=k;}
}
void cal(int u,int need){for(int i=0;i<20;i++){int x=u>>i&1;ans+=(1ll<<i)*(f[x^1][i][a[u]^need]);}
}
void dfs(int u,int fa=0,int keep=0){for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa||j==son[u])continue;dfs(j,u,0);}if(son[u])dfs(son[u],u,1);ins(u);//先去递归，再插入我自己,不然会wafor(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa||j==son[u])continue;for(int x=L[j];x<=R[j];x++)cal(id[x],a[u]);for(int x=L[j];x<=R[j];x++)ins(id[x]);}if(!keep)for(int i=L[u];i<=R[u];i++)ins(id[i],-1);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(h,-1,sizeof h);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b);add(b,a);}dsu(1);dfs(1);cout<<ans;
}

E. Blood Cousins Return

树上gcd(x,y)==x^y的个数，操作1，插入新节点a[x]=v,操作2，合并x和y子树，操作3，把a[x]->v

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int n,m,p[N],sz[N],a[N];
ll ans;
vector<int>g[N];//g[i]表示i可能的答案，枚举i的约数存入进去
unordered_map<int,int>mp[N];
int find(int x){if(p[x]==x)return x;return p[x]=find(p[x]);
}
// a^b==gcd(a,b)有多少对
//a^b>=|a-b|>=gcd(a,b)void merge(int x,int y){x=find(x),y=find(y);if(x==y)return;if(sz[x]<sz[y])swap(mp[x],mp[y]),swap(sz[x],sz[y]);for(auto [k,v]:mp[y]){for(auto t:g[k])if(mp[x].count(t))ans+=(ll)mp[x][t]*v;}for(auto [k,v]:mp[y])mp[x][k]+=v;mp[y].clear();p[y]=x;sz[x]+=sz[y];
}
void so(int x){for(int d=1;d*d<=x;d++){if(x%d)continue;int i=d,j=x/i,y;y=x-i;if((x^y)==__gcd(x,y)&&y>0)g[x].push_back(y);y=x+i;if((x^y)==__gcd(x,y)&&y<=2e5)g[x].push_back(y);if(i==j)continue;y=x-j;if((x^y)==__gcd(x,y)&&y>0)g[x].push_back(y);y=x+j;if((x^y)==__gcd(x,y)&&y<=2e5)g[x].push_back(y);}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// for(int i=1;i<=2e5;i++)so(i);for (int i = 1; i <= 200000; i++) {for (int j = i + i; j <= 200000; j += i) {if (gcd(j, i^j) == i)g[j].push_back(i^j);}}cin>>n>>m;for(int i=1;i<=n+m;i++)p[i]=i,sz[i]=1;for(int i=1;i<=n;i++)cin>>a[i],mp[i][a[i]]++;while(m--){int op,x;cin>>op;if(op==1){int v;cin>>x>>v;a[x]=v;mp[x][v]=1;}if(op==2){int y;cin>>x>>y;merge(x,y);}if(op==3){int v;cin>>x>>v;int u=find(x);for(auto t:g[a[x]])if(mp[u].count(t))ans-=mp[u][t];mp[u][a[x]]--;a[x]=v;for(auto t:g[a[x]])if(mp[u].count(t))ans+=mp[u][t];mp[u][a[x]]++;}cout<<ans<<'\n';}
}

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=3e5+10;
int n,m,a[N],p[N];
long long ans;
vector<int>g[N];
int find(int x){if(p[x]==x)return x;return p[x]=find(p[x]);
}
void init(){for(int i=1;i<=2e5;i++){for(int j=i+i;j<=2e5;j+=i){if(__gcd(j,i^j)==i)g[j].push_back(i^j);}}
}
unordered_map<int,int>mp[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();cin>>n>>m;for(int i=1;i<N;i++)p[i]=i;for(int i=1;i<=n;i++)cin>>a[i],mp[i][a[i]]=1;while(m--){int op,x,v;cin>>op>>x>>v;if(op==1)a[x]=v,p[x]=x,mp[x][v]=1;if(op==2){x=find(x),v=find(v);if(x!=v){if(mp[x].size()<mp[v].size())swap(mp[x],mp[v]);for(auto [a,c]:mp[v]){for(auto need:g[a])if(mp[x].count(need))ans+=(long long)c*mp[x][need];}for(auto [a,c]:mp[v])mp[x][a]+=c;// mp[v].clear();p[v]=x;}}if(op==3){int fa=find(x);int c=1;for(auto need:g[a[x]])if(mp[fa].count(need))ans-=c*mp[fa][need];mp[fa][a[x]]--;a[x]=v;for(auto need:g[a[x]])if(mp[fa].count(need))ans+=c*mp[fa][need];mp[fa][a[x]]++;}cout<<ans<<'\n';}}

---