小红的奇数奶油球

链接

emm,又一次败给了dfs

这道题我们可以给每一个节点记录它的相邻节点的信息,但是我们并不知道该节点有多少相邻节点

可以设置一个vector tree[[MAX]] (tree[i]就是vector数组,当然map<int,vector>也行)的数组,这样第i个节点tree[i]的数量就可以随时改变了

接着我们按低序号为父节点,一个一个遍历就行了

#include<iostream>
#include<vector>
using namespace std;
#define MAX 200005
vector<int> tree[MAX];
int node[MAX];
int n;
int ans;
void f(int current, int last) {
	node[current] = 1;
	bool valid = true;
	for (int next : tree[current]) {
		if (next == last) continue;//防止回去
		f(next, current);
		node[current] += node[next];
		if (node[next] % 2 == 0) {
			valid = false;
		}
	}

	if (n>node[current] && (n - node[current]) % 2 == 0) {
		valid = false;
	}

	if (valid) ans++;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1;i <= n;i++) {
			tree[i].clear();
		}

		for (int i = 0;i < n - 1;i++) {
			int u, v;
			cin >> u >> v;
			tree[u].push_back(v);
			tree[v].push_back(u);
		}
		ans = 0;
		f(1, 0);
		cout << ans << '\n';
	}
}