Lomsat gelral

一棵以\(1\)为根的树有\(n\)个结点，每个结点都有一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号（若有数量一样的，则求编号和）。

\(n \le 10^5\)

题解

dsu on tree模板题。

暴力做法其实很简单，就是枚举这个点，然后扫一遍子树得到答案，然后清空cnt数组。

我们会发现它做了一些无用功，比如说最后一次清空，其实可以用于他的父节点，这样父节点就可以少算一个子节点。

我们想让尽量大的子树不擦除，那么就树剖剖出重儿子，重儿子不擦除就可以了。

这样一个点会被祖先统计到当且仅当它在轻儿子子树中，所以一个点被统计不超过\(O(\log n)\)次。总时间复杂度\(O(n\log n)\)。

#include<bits/stdc++.h>

#define co const

#define il inline

template<class T> T read(){

	T x=0,w=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*w;

}

template<class T>il T read(T&x){

	return x=read<T>();

}

using namespace std;

typedef long long LL;

co int N=100001;

int n,val[N];

vector<int> e[N];

int fa[N],siz[N],son[N];

void dfs1(int x,int fa){

	siz[x]=1;

	for(unsigned i=0;i<e[x].size();++i){

		int y=e[x][i];

		if(y==fa) continue;

		::fa[y]=x;

		dfs1(y,x);

		siz[x]+=siz[y];

		if(siz[y]>siz[son[x]]) son[x]=y;

	}

}

LL ans[N];

int cnt[N],vis[N];

int maxc;LL sum;

void change(int x,int d){

	cnt[val[x]]+=d;

	if(d>0&&cnt[val[x]]>=maxc){

		if(cnt[val[x]]>maxc) sum=0,maxc=cnt[val[x]];

		sum+=val[x];

	}

	for(unsigned i=0;i<e[x].size();++i){

		int y=e[x][i];

		if(y==fa[x]||vis[y]) continue;

		change(y,d);

	}

}

void dfs2(int x,int use){

	for(unsigned i=0;i<e[x].size();++i){

		int y=e[x][i];

		if(y==fa[x]||y==son[x]) continue;

		dfs2(y,0);

	}

	if(son[x]) dfs2(son[x],1),vis[son[x]]=1;

	change(x,1),ans[x]=sum;

	if(son[x]) vis[son[x]]=0;

	if(!use) change(x,-1),maxc=sum=0;

}

int main(){

	read(n);

	for(int i=1;i<=n;++i) read(val[i]);

	for(int i=1,x,y;i<n;++i){

		read(x),read(y);

		e[x].push_back(y),e[y].push_back(x);

	}

	dfs1(1,0);

	dfs2(1,0);

	for(int i=1;i<=n;++i) printf("%lld ",ans[i]);

	return 0;

}

Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

一棵以\(1\)号点为根的树，每条边上有一个小写字母\(a\sim v\)。定义一条路经是好的，当且仅当这条路径上经过的所有小写字母重排后可以构成回文串。

求以每个点为根的子树中最长的好的路径。

\(n \le 10^5\)

题解

如果重排后能形成回文串，那么出现奇数次的字符最多有1个。

首先，对于一条字母是\(c\)的边，定义其权值为\(2^c\)。

这样一条路经是好的就当且仅当这条路径的异或和二进制位中的\(1\)的个数不超过\(1\)。

在处理以某一点为根的子树时，开桶，记\(f[i]\)表示到根路径异或和为\(i\)的点的最大深度，可以类似点分的方法计算答案并更新桶。

然后套个dsu on tree，这道题就解决了。时间复杂度\(O(n \log n)\)。

#include<bits/stdc++.h>

#define co const

#define il inline

template<class T> T read(){

	T x=0,w=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*w;

}

template<class T>il T read(T&x){

	return x=read<T>();

}

using namespace std;

co int N=500000+5;

int n,nx[N],to[N],val[N];

int siz[N],son[N],dep[N];

int pos[N],dfn,id[N],lst[N];

void dfs1(int x){

	siz[x]=1,id[pos[x]=++dfn]=x;

	for(int y=to[x];y;y=nx[y]){

		dep[y]=dep[x]+1,val[y]=val[y]^val[x];

		dfs1(y);

		siz[x]+=siz[y];

		if(siz[y]>siz[son[x]]) son[x]=y;

	}

	lst[x]=dfn;

}

int f[1<<22],ans[N];

void dfs2(int x,int use){

	for(int y=to[x];y;y=nx[y])

		if(y!=son[x]) dfs2(y,0),ans[x]=max(ans[x],ans[y]);

	if(son[x]) dfs2(son[x],1),ans[x]=max(ans[x],ans[son[x]]);

//	cerr<<x<<" ans="<<ans[x]<<endl;

	if(f[val[x]]) ans[x]=max(ans[x],f[val[x]]-dep[x]);

	for(int i=0;i<22;++i)if(f[val[x]^(1<<i)])

		ans[x]=max(ans[x],f[val[x]^(1<<i)]-dep[x]);

	f[val[x]]=max(f[val[x]],dep[x]);

//	cerr<<x<<" ans="<<ans[x]<<endl;

	for(int y=to[x];y;y=nx[y])if(y!=son[x]){

		for(int i=pos[y];i<=lst[y];++i){

			int z=id[i];

			if(f[val[z]]) ans[x]=max(ans[x],f[val[z]]+dep[z]-(dep[x]<<1));

			for(int j=0;j<22;++j)if(f[val[z]^(1<<j)])

				ans[x]=max(ans[x],f[val[z]^(1<<j)]+dep[z]-(dep[x]<<1));

		}

		for(int i=pos[y];i<=lst[y];++i){

			int z=id[i];

			f[val[z]]=max(f[val[z]],dep[z]);

		}

	}

//	cerr<<x<<" ans="<<ans[x]<<endl;

	if(!use) for(int i=pos[x];i<=lst[x];++i) f[val[id[i]]]=0;

}

int main(){

	read(n);

	for(int i=2;i<=n;++i){

		int fa=read<int>();char ch=getchar();

		nx[i]=to[fa],to[fa]=i,val[i]=1<<(ch-'a');

	}

	dfs1(1);

	dfs2(1,0);

	for(int i=1;i<=n;++i) printf("%d ",ans[i]);

	return 0;

}

巴特西

CF600E Lomsat gelral 和 CF741D Dokhtar-kosh paths

Lomsat gelral

题解

Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

题解

最新文章

热门文章