CF 741D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths [dsu on tree 类似点分治]

2022-07-09 16:38:46

####　D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
[CF741D](http://codeforces.com/contest/741/problem/D)
题意：
一棵有根树，边上有字母a~v，求每个子树中最长的边，满足这个边上的所有字母重拍后可以构成回文

发明者自己出的题...orz

由于本来知道就是dsu on tree，所以还是想出来了

首先点分治是没法做了，这是有根树

写成二进制，两条链合起来构成回文\(\rightarrow\)异或和为0或者只有一位是1

一开始困惑于只处理到当前根的异或和的话，随着当前根的变化异或值会变

然后发现我们可以处理到根的异或和，两条链异或之后\(lca\)之上的部分正好没有了

用\(f[i]\)记录到根的异或和为\(i\)的最大深度

进行dsu on tree

当前子树的答案先\(max\)一下孩子的答案，然后类似于点分治处理经过当前根的路径

和点分治一样，一个一个轻儿子处理，先更新答案再更新信息\(f\)

如果当前是父亲的轻儿子，那么要清空\(f\)的信息

说一下起初的错误：

单独用了一个\(g\)记录轻儿子，这是不对的，因为当前的子树要么是重儿子，应该一直保留；要么是轻儿子，到时候全清除就可以了。
一定不能整体操作重儿子的信息，要不然复杂度就不对了
这里有一个\(trick\)，因为有根树处理一棵子树我们可以提前搞出\(dfs\)序就不用每次\(dfs\)了，常数优化显著

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define MP make_pair

#define fir first

#define sec second

const int N=5e5+5, M=1e7+5;

int read(){

    char c=getchar();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}

    return x*f;

}

int n, x;

char s[5];

struct edge{int v, ne, c;}e[N<<1];

int cnt, h[N];

inline void ins(int u, int v, int c) {

	e[++cnt]=(edge){v, h[u], c}; h[u]=cnt;

}

int Xor[N], dfc, ver[N];

pii dfn[N];

void dfsPre(int u) {

	dfn[u].fir = ++dfc; ver[dfc] = u;

	for(int i=h[u];i;i=e[i].ne) Xor[e[i].v] = Xor[u]^e[i].c, dfsPre(e[i].v);

	dfn[u].sec = dfc;

}

int size[N], mx[N], deep[N];

void dfs(int u) {

	size[u]=1;

	for(int i=h[u];i;i=e[i].ne) {

		deep[e[i].v] = deep[u]+1;

		dfs(e[i].v);

		size[u] += size[e[i].v];

		if(size[e[i].v] > size[mx[u]]) mx[u] = e[i].v;

	}

}

int ans[N], f[M];

void dfs(int u, int keep) {

	int &cur = ans[u];

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].v != mx[u]) dfs(e[i].v, 0), cur = max(cur, ans[e[i].v]);

	if(mx[u]) dfs(mx[u], 1), cur = max(cur, ans[mx[u]]);

	int now = Xor[u], d = deep[u];

	if(f[now]) cur = max(cur, f[now] - d);

	for(int i=0; i<=21; i++)

		if(f[now^(1<<i)]) cur = max(cur, f[now^(1<<i)] - d);

	f[now] = max(f[now], d);

	for(int i=h[u];i;i=e[i].ne) if(e[i].v != mx[u]) {

		int l = dfn[e[i].v].fir, r = dfn[e[i].v].sec;

		for(int j=l; j<=r; j++) {

			int x = ver[j], now = Xor[x];

			if(f[now]) cur = max(cur, f[now] + deep[x] - (d<<1));

			for(int i=0; i<=21; i++)

				if(f[now^(1<<i)]) cur = max(cur, f[now^(1<<i)] + deep[x] - (d<<1));

		}

		for(int j=l; j<=r; j++)

			f[ Xor[ver[j]] ] = max(f[ Xor[ver[j]] ], deep[ver[j]]);

	}

	if(!keep) {

		int l = dfn[u].fir, r = dfn[u].sec;

		for(int j=l; j<=r; j++) f[ Xor[ver[j]] ] = 0;

	}

}

int main() {

	//freopen("in","r",stdin);

	n=read();

	for(int i=2; i<=n; i++) x=read(), scanf("%s",s), ins(x, i, 1<<(s[0]-'a') );

	dfsPre(1);

	deep[1]=1; dfs(1);

	dfs(1, 0);

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

}

这里是没用dfs序的版本

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define MP make_pair

#define fir first

#define sec second

const int N=5e5+5, M=1e7+5;

int read(){

    char c=getchar();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}

    return x*f;

}

int n, x;

char s[5];

struct edge{int v, ne, c;}e[N<<1];

int cnt, h[N];

inline void ins(int u, int v, int c) { //printf("ins %d %d %d\n",u,v,c);

	e[++cnt]=(edge){v, h[u], c}; h[u]=cnt;

}

int Xor[N];

void dfsXor(int u) {

	for(int i=h[u];i;i=e[i].ne) Xor[e[i].v] = Xor[u]^e[i].c, dfsXor(e[i].v);

}

int size[N], mx[N], deep[N], big[N];

void dfs(int u) {

	size[u]=1;

	for(int i=h[u];i;i=e[i].ne) {

		deep[e[i].v] = deep[u]+1;

		dfs(e[i].v);

		size[u] += size[e[i].v];

		if(size[e[i].v] > size[mx[u]]) mx[u] = e[i].v;

	}

}

int ans[N], f[M];

void update(int u, int &ans, int d) {

	int now = Xor[u];

	if(f[now]) ans = max(ans, f[now] + deep[u] - 2*d);

	for(int i=0; i<=21; i++) {

		int t = now^(1<<i);

		if(f[t]) ans = max(ans, f[t] + deep[u] - 2*d);

	}

	for(int i=h[u];i;i=e[i].ne) if(!big[e[i].v]) update(e[i].v, ans, d);

}

void merge(int u) {

	int now = Xor[u];

	f[now] = max(f[now], deep[u]);

	for(int i=h[u];i;i=e[i].ne) if(!big[e[i].v]) merge(e[i].v);

}

void clear(int u) {

	int now = Xor[u];

	f[now] = 0;

	for(int i=h[u];i;i=e[i].ne) if(!big[e[i].v]) clear(e[i].v);

}

void dfs(int u, int keep) { //printf("dfs %d %d   mx %d\n",u,keep,mx[u]);

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].v != mx[u]) dfs(e[i].v, 0), ans[u] = max(ans[u], ans[e[i].v]);

	if(mx[u]) dfs(mx[u], 1), big[mx[u]]=1, ans[u] = max(ans[u], ans[mx[u]]);

	int now = Xor[u], d = deep[u];

	if(f[now]) ans[u] = max(ans[u], f[now] + deep[u] - 2*d);

	for(int i=0; i<=21; i++) {

		int t = now^(1<<i);

		if(f[t]) ans[u] = max(ans[u], f[t] + deep[u] - 2*d);

	}

	f[now] = max(f[now], d);

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].v != mx[u]) update(e[i].v, ans[u], deep[u]), merge(e[i].v);

	big[mx[u]]=0;

	if(!keep) clear(u);

}

int main() {

	//freopen("in","r",stdin);

	n=read();

	for(int i=2; i<=n; i++) x=read(), scanf("%s",s), ins(x, i, 1<<(s[0]-'a') );

	dfsXor(1);

	//puts("");for(int i=1; i<=n; i++) printf("Xor %d %d\n",i,Xor[i]);puts("");

	deep[1]=1; dfs(1);

	dfs(1, 0);

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

}

码农公寓

相关文章