江门市住房和城乡建设部网站,制作电子商务网站页面,最有效的免费推广方法,合肥网达软件有限公司Codeforces-741D(Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths)
一棵根为1 的树#xff0c;每条边上有一个字符#xff08;a-v共22种#xff09;。 一条简单路径被称为Dokhtar-kosh当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中…Codeforces-741D(Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths)
一棵根为1 的树每条边上有一个字符a-v共22种。 一条简单路径被称为Dokhtar-kosh当且仅当路径上的字符经过重新排序后可以变成一个回文串。 求每个子树中最长的Dokhtar-kosh路径的长度。给你n个点构成的一棵树树里面的每一条边有一个权值求出每个子树里面能通过重排构成回文串的最大路径长度.
#includebits/stdc.h
using namespace std;
const int N5e510,M2*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[123],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 fa0){dep[u]dep[fa]1;dfn[u]o,id[o]u;sz[u]1;L[u]o;for(int ih[u];~i;ine[i]){int je[i];if(jfa)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 i0;i22;i){int xd[u]^(1i);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 i0;i22;i){int xd[j]^(1i);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 ih[u];~i;ine[i]){int je[i];if(json[u]||jfa)continue;for(int xL[j];xR[j];x)upd2(id[x],u);//计算子树所有节点和我构成的贡献for(int xL[j];xR[j];x)f[d[id[x]]]max(f[d[id[x]]],dep[id[x]]);//插入这颗子树的贡献}
}
void dfs(int u,int fa0,int keep0){for(int ih[u];~i;ine[i]){int je[i];if(jfa||json[u])continue;//先枚举轻儿子不保留dfs(j,u,0);ans[u]max(ans[u],ans[j]);}if(son[u]){//再计算重儿子保留答案int json[u];dfs(j,u,1);ans[u]max(ans[u],ans[j]);flagj;}cal(u,fa);//计算跟u节点相关的答案flag0;if(!keep)for(int iL[u];iR[u];i)f[d[id[i]]]0;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;memset(h,-1,sizeof h);char c;for(int i2,j;in;i)cinjc,add(j,i,1(c-a)),add(i,j,1(c-a));dfs1(1);dfs(1);for(int i1;in;i)coutans[i] ;
}阔力梯的树 用启发式合并写
#includebits/stdc.h
using namespace std;
#define int long long
const int N1e510;
int n,sz[N];
long long f[N];
vectorintg[N],son[N];
setintS[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 itS[u].lower_bound(x);if(itS[u].begin())f[u](x-*it)*(x-*it);else if(itS[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);cinn;for(int i2;in;i){int fa;cinfa;g[fa].push_back(i);}dfs(1);for(int i1;in;i)coutf[i]\n;
}用树链剖分写
#includebits/stdc.h
using namespace std;
#define int long long
const int N1e510;
int n,h[N],ne[N],e[N],idx;
int sz[N],id[N],L[N],R[N],o,son[N],ans[N];
setintS;
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 ih[u];~i;ine[i]){int je[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 itS.lower_bound(x);if(itS.begin())f(x-*it)*(x-*it);else if(itS.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 keep0){for(int ih[u];~i;ine[i]){int je[i];if(json[u])continue;dfs(j,0);}if(son[u])dfs(son[u],1);for(int ih[u];~i;ine[i]){int je[i];if(json[u])continue;for(int kL[j];kR[j];k)ins(id[k]);}ins(u);ans[u]f;if(!keep)f0,S.clear();
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;memset(h,-1,sizeof h);for(int i2;in;i){int fa;cinfa;add(fa,i);}dsu(1);dfs(1);for(int i1;in;i)coutans[i]\n;
}F. Strange Memory #includebits/stdc.h
// #define int long long
using namespace std;
const int N2e510,M1e65e5;
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 fa0){sz[u]1;L[u]o;id[o]u;for(int ih[u];~i;ine[i]){int je[i];if(jfa)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 k1){for(int i0;i20;i){int xui1;f[x][i][a[u]]k;}
}
void cal(int u,int need){for(int i0;i20;i){int xui1;ans(1lli)*(f[x^1][i][a[u]^need]);}
}
void dfs(int u,int fa0,int keep0){for(int ih[u];~i;ine[i]){int je[i];if(jfa||json[u])continue;dfs(j,u,0);}if(son[u])dfs(son[u],u,1);ins(u);//先去递归再插入我自己,不然会wafor(int ih[u];~i;ine[i]){int je[i];if(jfa||json[u])continue;for(int xL[j];xR[j];x)cal(id[x],a[u]);for(int xL[j];xR[j];x)ins(id[x]);}if(!keep)for(int iL[u];iR[u];i)ins(id[i],-1);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(h,-1,sizeof h);cinn;for(int i1;in;i)cina[i];for(int i1;in;i){int a,b;cinab;add(a,b);add(b,a);}dsu(1);dfs(1);coutans;
}E. Blood Cousins Return
树上gcd(x,y)x^y的个数操作1插入新节点a[x]v,操作2合并x和y子树操作3把a[x]-v
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N3e510;
int n,m,p[N],sz[N],a[N];
ll ans;
vectorintg[N];//g[i]表示i可能的答案枚举i的约数存入进去
unordered_mapint,intmp[N];
int find(int x){if(p[x]x)return x;return p[x]find(p[x]);
}
// a^bgcd(a,b)有多少对
//a^b|a-b|gcd(a,b)void merge(int x,int y){xfind(x),yfind(y);if(xy)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 d1;d*dx;d){if(x%d)continue;int id,jx/i,y;yx-i;if((x^y)__gcd(x,y)y0)g[x].push_back(y);yxi;if((x^y)__gcd(x,y)y2e5)g[x].push_back(y);if(ij)continue;yx-j;if((x^y)__gcd(x,y)y0)g[x].push_back(y);yxj;if((x^y)__gcd(x,y)y2e5)g[x].push_back(y);}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// for(int i1;i2e5;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);}}cinnm;for(int i1;inm;i)p[i]i,sz[i]1;for(int i1;in;i)cina[i],mp[i][a[i]];while(m--){int op,x;cinop;if(op1){int v;cinxv;a[x]v;mp[x][v]1;}if(op2){int y;cinxy;merge(x,y);}if(op3){int v;cinxv;int ufind(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))ansmp[u][t];mp[u][a[x]];}coutans\n;}
}#includebits/stdc.h
// #define int long long
using namespace std;
const int N3e510;
int n,m,a[N],p[N];
long long ans;
vectorintg[N];
int find(int x){if(p[x]x)return x;return p[x]find(p[x]);
}
void init(){for(int i1;i2e5;i){for(int jii;j2e5;ji){if(__gcd(j,i^j)i)g[j].push_back(i^j);}}
}
unordered_mapint,intmp[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);init();cinnm;for(int i1;iN;i)p[i]i;for(int i1;in;i)cina[i],mp[i][a[i]]1;while(m--){int op,x,v;cinopxv;if(op1)a[x]v,p[x]x,mp[x][v]1;if(op2){xfind(x),vfind(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(op3){int fafind(x);int c1;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))ansc*mp[fa][need];mp[fa][a[x]];}coutans\n;}}
