CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths（樹上啟發式合并）

題意

題面比題目還短。

給一棵樹，邊上有一個字母（隻有a到v共22個）。一條簡單路徑被稱為Dokhtar-kosh當且僅當路徑上的字元經過重新排序後可以變成一個回文串。

求每個子樹中最長的Dokhtar-kosh路徑的長度。

鬼畜：

思路

一條路徑符合要求，當他隻有0或1種字母出現奇數次，是以用一個二進制數記錄一條路徑。

一條簡單路徑可以看成兩條從根出發的鍊連在一起，表示為 x    x o r    y x\;xor\;y xxory，順便還把lca到根的那一段重複給去掉了。

因為求得是每一棵子樹的答案，套上樹上啟發式合并闆子。對于每一棵子樹，先更新答案再update，防止用兩條同一子樹的鍊更新答案。

萌新剛學樹上Dsu，熟悉一下模闆。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 5e5+10;
const int E = 1<<22;
const int B = 22;
int n, point[N];
struct EDGE{
	int nxt, v, w;
}edge[N<<1];
int val[N], dpt[N], sz[N], son[N], ans[N];
int dfn[N], rfn[N], ed[N], idx, len[E];

inline void chkMax(int &x, int y){if (x < y) x = y;}

inline void add_edge(int u, int v, int w, int e)
{
	edge[e] = (EDGE){point[u], v, w};
	point[u] = e;
}

void Dfs1(int u, int fa)
{
	dpt[u] = dpt[fa]+1;
	sz[u] = 1;
	son[u] = -1;
	for (int i = point[u]; i != -1; i = edge[i].nxt){
		int v = edge[i].v;
		int w = edge[i].w;
		if (v == fa) continue;
		val[v] = val[u]^(1<<w);
		Dfs1(v, u);
		sz[u] += sz[v];
		if (son[u] == -1 || sz[v] > sz[son[u]])
			son[u] = v;
	}
}

int Calc(int u)
{
	int ret = 0;
	if (len[val[u]])
		ret = dpt[u]+len[val[u]];
	for (int i = 0; i < B; ++ i)
		if (len[val[u]^(1<<i)])
			chkMax(ret, dpt[u]+len[val[u]^(1<<i)]);
	return ret;
}

void Add(int u)
{
	chkMax(len[val[u]], dpt[u]);
}

void Del(int u)
{
	len[val[u]] = 0;
}

void Dfs2(int u, int fa, int tp)
{
	int lght, delta = dpt[u]<<1;
	dfn[++ idx] = u;
	rfn[u] = idx;
	ans[u] = 0;
	
	for (int i = point[u]; i != -1; i = edge[i].nxt){
		int v = edge[i].v;
		if (v == fa || v == son[u]) continue;
		Dfs2(v, u, v);
		chkMax(ans[u], ans[v]);
	}
	lght = idx;
	
	if (son[u] != -1){
		Dfs2(son[u], u, tp);
		chkMax(ans[u], ans[son[u]]);
	}
	ed[u] = idx;
	
	for (int i = rfn[u]+1; i <= lght; i = ed[dfn[i]]+1){
		for (int j = i; j <= ed[dfn[i]]; ++ j) // 要非常清楚i,rfn[u],dfn[i]等的意義
			chkMax(ans[u], Calc(dfn[j])-delta);
		for (int j = i; j <= ed[dfn[i]]; ++ j)
			Add(dfn[j]);
	}
	chkMax(ans[u], Calc(u)-delta);
	Add(u);
	
	if (u == tp){
		for (int i = rfn[u]; i <= ed[u]; ++ i)
			Del(dfn[i]);
	}
}

int main()
{
	scanf("%d", &n);
	memset(point, -1, sizeof(point));
	for (int i = 2; i <= n; ++ i){
		int x; scanf("%d", &x);
		char c = getchar(); while (c < 'a' || c > 'v') c = getchar();
		add_edge(i, x, c-'a', (i-2)<<1);
		add_edge(x, i, c-'a', (i-2)<<1^1);
	}
	dpt[0] = -1; val[1] = 0;
	
	Dfs1(1, 0);
	
	memset(len, 0, sizeof(len));
	idx = 0;
	
	Dfs2(1, 0, 1);
	
	for (int i = 1; i <= n; ++ i)
		printf("%d ", ans[i]);
	return 0;
}