纯暴力

#include <bits/stdc++.h>  
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
using namespace std;  

/*
T3:
如何用数组存储树：

假设当前节点下标是 i ，那么它的左孩子的下标 i*2，右孩子的下标 i*2+1

一个字符集，它能组成回文的条件是：所有字符中，最多只能有一个字符出现的次数是奇数

统计以每个节点作为根节点的树，字符的出现次数

统计以这个节点为根的树，字符的出现总数
*/

const int N = 1e5+5;

int n, q, cnt[30], res;
char tree[N];

void dfs(int i) {
	cnt[tree[i]-'a']++;  // 统计当前的
	if (i*2 <=n) dfs(i*2);
	if (i*2+1 <=n) dfs(i*2+1);
}

bool check() {
	// 统计cnt数组中的奇偶数量
	int sum = 0;
	for (int i=0; i<26; i++) {
		sum += cnt[i]%2;
	}
	return sum <= 1;
}

void solve() {
	res = 0;
	
	for (int i=1; i<=n; i++) {
		memset(cnt, 0, sizeof cnt);
		dfs(i);
		// 处理cnt里的所有情况，统计出现次数的奇偶数量
		if (check()) res++;
	}
	
	cout << res << '\n';
}

signed main() {  
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	qwq;  
	
	cin >> n >> q;
	for (int i=1; i<=n; i++) cin >> tree[i];
	
	solve();
	
	while (q--) {
		int x;
		char c;
		cin >> x >> c;
		tree[x] = c;
		solve();
	}
	return 0;  
}

利用桶记录每一个节点的字符数量，这样只需要dfs一次。

#include <bits/stdc++.h>  
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
using namespace std;  

/*
T3:
如何用数组存储树：

假设当前节点下标是 i ，那么它的左孩子的下标 i*2，右孩子的下标 i*2+1

一个字符集，它能组成回文的条件是：所有字符中，最多只能有一个字符出现的次数是奇数

统计以每个节点作为根节点的树，字符的出现次数

统计以这个节点为根的树，字符的出现总数
*/

const int N = 1e5+5;

int n, q, cnt[N][30], res;
// cnt[i][j] 表示的是以i节点为根的树，字母j出现的次数
char tree[N];

void dfs(int i) {
	cnt[i][tree[i]-'a']++;  // 统计当前的
	
	if (i*2 <=n) {
		dfs(i*2);  // cnt[i*2]
		for (int j=0; j<26; j++) cnt[i][j] += cnt[i*2][j];
	}
	if (i*2+1 <=n) {
		dfs(i*2+1);  // cnt[i*2+1]
		for (int j=0; j<26; j++) cnt[i][j] += cnt[i*2+1][j];
	}
}

bool check(int i) {
	int sum = 0;
	for (int j=0; j<26; j++) {
		sum += (cnt[i][j] % 2);
	}
	return sum <= 1;
}

void solve() {
	res = 0;
	for (int i=1; i<=n; i++) {
		if (check(i)) res++;
	}
	
	cout << res << '\n';
}

signed main() {  
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	qwq;  
	
	cin >> n >> q;
	for (int i=1; i<=n; i++) cin >> tree[i];
	
	dfs(1);  // 遍历根节点
	solve();
	
	while (q--) {
		int x;
		char c;
		cin >> x >> c;
		tree[x] = c;
		memset(cnt, 0, sizeof cnt);
		dfs(1);
		solve();
	}
	return 0;  
}

正解：

#include <bits/stdc++.h>  
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
using namespace std;  

/*
T3:
如何用数组存储树：

假设当前节点下标是 i ，那么它的左孩子的下标 i*2，右孩子的下标 i*2+1

一个字符集，它能组成回文的条件是：所有字符中，最多只能有一个字符出现的次数是奇数

统计以每个节点作为根节点的树，字符的出现次数

统计以这个节点为根的树，字符的出现总数
*/

const int N = 1e5+5;

int n, q, cnt[N][30], res;
// cnt[i][j] 表示的是以i节点为根的树，字母j出现的次数
int mask[N];  // mask[i]标记节点i目前是否是满足答案的
char tree[N];

void dfs(int i) {
	cnt[i][tree[i]-'a']++;  // 统计当前的
	
	if (i*2 <=n) {
		dfs(i*2);  // cnt[i*2]
		for (int j=0; j<26; j++) cnt[i][j] += cnt[i*2][j];
	}
	if (i*2+1 <=n) {
		dfs(i*2+1);  // cnt[i*2+1]
		for (int j=0; j<26; j++) cnt[i][j] += cnt[i*2+1][j];
	}
}

bool check(int i) {
	int sum = 0;
	for (int j=0; j<26; j++) {
		sum += (cnt[i][j] % 2);
	}
	return sum <= 1;
}

void solve() {
	res = 0;
	for (int i=1; i<=n; i++) {
		if (check(i)) {
			res++;
			mask[i] = 1;  // 标记节点i是满足答案的
		}
	}
	
	cout << res << '\n';
}

void up(int x, char last, char c) {
	while (x > 0) {
		// x是被修改的字母的下标，c是新的字母
		cnt[x][c-'a']++;
		cnt[x][last-'a']--;
		
		// 如果之前x不满足答案，现在满足答案，res++;
		if (check(x)) {
			if (mask[x] == 0) res++;
			mask[x] = 1;
		}
		else {
			if (mask[x] == 1) res--;
			mask[x] = 0;
		}
		// 如果之前x满足答案，但现在不满足答案，res--;
		x /= 2;
	}
}

signed main() {  
//	freopen("tree.in", "r", stdin);
//	freopen("tree.out", "w", stdout);
	qwq;  
	
	cin >> n >> q;
	for (int i=1; i<=n; i++) cin >> tree[i];
	
	dfs(1);  // 遍历根节点
	solve();
	
	while (q--) {
		int x;
		char c;
		cin >> x >> c;
		up(x, tree[x], c);
		tree[x] = c;
		cout << res << '\n';
	}
	return 0;  
}