题目描述 现在给你一个按层序遍历顺次编号1,2,...,𝑛的完全二叉树。初始时，二叉树上每个节点初始都有一个字母。

接下来会有𝑞次操作，每次操作修改一个节点上的字母。

你需要回答每次修改完成后，二叉树上有多少节点，其子树内的字符集可以经过重新排列形成回文串。

保证所有出现的字母均为小写字母。

分析:这题要运用一些树的概念才能解决。

步骤分为以下几步: 1.输入数据,用char数组存储每一个字符。这里要明白:

2.统计在没修改之前有多少个节点的子节点(包括自己)的字符集经过修改可以变成回文串。 这里要记住判断方式:

3.每修改一个字符,就要重新统计一次 (统计什么你们因该清楚吧) 这里要注意几个特殊情况: 如果以前是回文现在不是回文:ans--(ans指有多少个节点的子节点(包括自己)的字符集经过修改可以变成回文串) 如果以前不是回文现在是回文:ans++

4.(最简单的一步) 输出答案。

5.(不是步骤但是也很重要)数据范围:$n,q$最多也就$10^5$,开int可以解决。如果不放心就开long long。

错因:时间全都拿来做一二四题了,所以没时间做,没有交。

代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, q, cnt[N][30], book[N], res;
char c[N];

void dfs(int i)
{
	if (2*i <= n)
	{
		dfs(i*2);
		for (int j = 0; j < 26; j++) cnt[i][j] += cnt[2*i][j];
	}
	if (2*i+1 <= n)
	{
		dfs(i*2+1);
		for (int j = 0; j < 26; j++) cnt[i][j] += cnt[2*i+1][j];
	}
	cnt[i][c[i]-'a']++;
	int temp = 0;
	for (int j = 0; j < 26; j++) temp += (cnt[i][j]%2);
	if (temp <= 1)
	{
		res ++;
		book[i] = 1;
	}
}

void up(int i, char now, char old)
{
	// i i/2 i/4 i/8 ....
	while (i)
	{
		cnt[i][old-'a']--;
		cnt[i][now-'a']++;
		// 重新统计奇偶性
		int temp = 0;
		for (int j = 0; j < 26; j++) temp += (cnt[i][j]%2);
		
		if (temp <= 1)
		{
			if (!book[i]) res++; // 之前不可以，现在可以了
			book[i] = 1;
		}
		else
		{
			if (book[i]) res--; // 之前可以，现在不行了
			book[i] = 0;
		}
		i/=2;  // 更新父节点
	}
}

int main()
{
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> c[i];
	dfs(1);
	cout << res << endl;
	while (q--)
	{
		int x;
		char ch;
		cin >> x >> ch;
		up(x, ch, c[x]); // 节点编号，新字符，旧字符
		c[x] = ch;
		cout << res << endl;
	}
	return 0;
}