CF-Round #633-div2-D题&div1C

CF-Round #633-div2-D题&div1C

D. Edge Weight Assignment

传送门

这道题。是关于异或的树上构造问题。

题目大意：给你一棵没有权值的树，让你把每条边上都填上权值，要求叶子结点之间的简单路径边上的权值相异或的值等于0。
输出构造的权值中不同个数的权值最大个数和最小个数分别为多少。

本题思路：
我们看看样例：


上面两个样例就是两种情况：
先求最小值minn：
我们模拟一下其实可以发现，在构造权值的时候，我们最多只需要三个数可以满足题目要求
我们最多只需要1，2，3这三个数构造整棵树的权值。比如图2的结点1~5（1 ^ 2 = 3, 3 ^ 3 = 0)这种情况是两个叶子结点之间的路径长度为奇数。
进而我们还可以发现：如果两个叶子结点之间的路径距离全部为偶数时，我们可以只用1个数。因为相同的数经过偶数次异或等于0（计数次异或等于自己本身，这是异或的性质）（其中用两个数字也是可以的，但是是最少情况嘛）

所以求最小值的思路出来了，判断任意两个叶子结点的路径长度是否全部为偶数，是的话最小值minn = 1,否则为3.

再来求最大值maxx:
我们其实根据样例很容易知道：具有相同父结点的叶子结点，叶子节点与父结点之间的权值必须相同。
至于其他边的权值，可以全部都不一样。
构造权值如下：

题目中说了
并且n只达到了1e5，所以可以构造出我们要求的不同的权值。

所以我们先开始把maxx直接赋值为最大值，边的数量。
然后需要减去具有相同父结点的叶子结点的那些情况。
直接用vis[]记录。当访问到叶子结点时，先把maxx–，如果当它的父结点没有被访问过，就加回来，访问过就不加。vis[]标记为1.

代码部分：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

vector<int> g[N];
int vis[N];
int n;

int dfs(int now, int pre, int dep)
{
	if (g[now].size() == 1 && dep)
	{
		return dep & 1;
	}
	int t = g[now].size();
	for (int i = 0; i < t; i++)
	{
		if (g[now][i] == pre)
		{
			continue;
		}
		if (dfs(g[now][i], now, dep + 1))
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int minn = 1;
	for (int i = 1; i <= n; i++)
	{
		if (g[i].size() == 1)
		{
			if (dfs(i, -1, 0))
			{
				minn = 3;
				break;
			}
			else
			{
				break;
			}
		}
	}
	cout << minn << " ";
	int maxx = n - 1;
	for (int i = 1; i <= n; i++)
	{
		if (g[i].size() == 1)
		{
			maxx--;
			if (!vis[g[i][0]])
			{
				maxx++;
			}
			vis[g[i][0]] = 1;
		}
	}
	cout << maxx << endl;
	return 0;
}