CF914E Palindromes in a Tree（点分治）

题面

洛谷

CF

题解

题意：给你一颗 n 个顶点的树（连通无环图）。顶点从 1 到 n 编号，并且每个顶点对应一个在‘a’到‘t’的字母。 树上的一条路径是回文是指至少有一个对应字母的排列为回文。 对于每个顶点，输出通过它的回文路径的数量。 注意：从u到v的路径与从v到u的路径视为相同，只计数一次

性质：回文字符串至多一个字母次数为奇数

因为字母只有'a'~'t'

那么可以状压一下

然后就是套点分治就好了

注意：顶点经过的次数要除以2（因为每条路径算了两次）

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

const int N = 200010;

inline int gi() {

	RG int x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar();

	if (c == '-') c = getchar(), f = 1;

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

	return f ? -x : x;

}

struct node {

	int to, next;

}g[N<<1];

int last[N], gl;

inline void add(int x, int y) {

	g[++gl] = (node) {y, last[x]};

	last[x] = gl;

	return ;

}

int sum, f[N], siz[N], rt;

bool vis[N];

void getroot(int u, int fa) {

	siz[u] = 1; f[u] = 0;

	for (int i = last[u]; i; i = g[i].next) {

		int v = g[i].to; if (v == fa || vis[v]) continue;

		getroot(v, u);

		f[u] = max(f[u], siz[v]);

		siz[u] += siz[v];

	}

	f[u] = max(f[u], sum-siz[u]);

	if (f[rt] > f[u]) rt = u;

	return ;

}

char a[N];

int s[N], t[10050000];

void dfs(int x, int fa, int p, int S) {

	t[S ^= (1 << s[x])] += p;

	for (int i = last[x]; i; i = g[i].next) {

		int v = g[i].to;

		if (v == fa||vis[v]) continue;

		dfs(v, x, p, S);

	}

}

LL ans[N];

LL calc(int x, int fa, int S) {

	S ^= (1 << s[x]);

	LL cnt = t[S];//都为偶数个

	for (int i = 0; i < 20; i++) cnt += t[S^(1<<i)];//出现了一个次数为奇数个

	for (int i = last[x]; i; i = g[i].next) {

		int v = g[i].to;

		if (v == fa || vis[v]) continue;

		cnt += calc(v, x, S);

	}

	ans[x] += cnt;

	return cnt;

}

void solve(int x) {

	vis[x] = 1;

	dfs(x, 0, 1, 0);

	LL cnt = t[0];

	for (int i = 0; i < 20; i++) cnt += t[1<<i];

	//单个一条链

	for (int i = last[x]; i; i = g[i].next) {

		int v = g[i].to; if (vis[v]) continue;

		dfs(v, x, -1, 1<<s[x]);//去掉以v开头的链

		cnt += calc(v, x, 0); //计算组合起来的路径

		dfs(v, x, 1, 1<<s[x]);

	}

	dfs(x, 0, -1, 0);

	ans[x] += cnt/2;//算了两次啦

	for (int i = last[x]; i; i = g[i].next) {

		int v = g[i].to; if(vis[v]) continue;

		sum = siz[v];rt = 0;

		getroot(v, 0);

		solve(rt);

	}

	return ;

}

int main() {

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

	//freopen(".out", "w", stdout);

	int n = gi();

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

		int u = gi(), v = gi();

		add(u, v); add(v, u);

	}

	scanf("%s", a);

	for (int i = 0; i < n; i++) s[i+1] = a[i]-'a';

	f[0] = sum = n; rt = 0;

	getroot(1, 0); solve(rt);

	for (int i = 1; i <= n; i++)

		printf("%lld ", ans[i]+1);

	return 0;

}