D. Edge Weight Assignment（思维 + 构造）（有证明）

D. Edge Weight Assignment

好难哦…

分析

首先把树给固定下来，以任意叶子节点作为根；

1. 先考虑最小值：
   结论：如果树中所有叶子节点到根节点的距离都为偶数则用1种数就行，否则要用3种数；

证明：
(1) 1种数比较简单看出来，主要是只用1种数树中任意两叶子节点为啥异或值也是0？
这里考虑两个叶子节点ab，其lca(a,b) = p，由于所有叶子节点到根的距离是偶数；
所以p到a b的距离的奇偶性是相同的，所以任意a b之间的距离也是偶数，所以1种数就行；
(2) 如果距离是奇数呢？假设ab之间有n条边，显然用1/2个数都是不行的（自己模拟一下）；
我们可以用3个数构造出来，前面前面n-1条边用2个数异或成最后一条边的那个数（比如：2 3 1）。
还是那个问题，那如何证明用3个数就能使得树中其他叶子节点之间异或值也是0呢？
这里用更形式化的证明一下：（root是根，ab表示两个叶子节点，p是lca(a,b)，sum[x,y]表示x到y路径上的异或值之和）;
首先我们要知道^有一个类似前缀和的一个性质，且x ^ y = z <=> x = y ^ z
sum[root,a] = sum[root,p] ^ sum[p,a];
sum[root,b] = sum[root,p] ^ sum[p,b];
sum[a,b] = sum[p,a] ^ sum[p,b] = sum[root,a] ^ sum[root,p] ^ sum[root,b] ^ sum[root,p]
= (sum[root,a] ^ sum[root,b]) ^ (sum[root,b] ^ sum[root,b]) = 0 ^ 0 = 0;
证毕。

2. 再考虑最大值：
   结论：
   我们发现如果一个节点u向下直接连了>=2个叶子结点，那么u到其子叶子节点之间的边都得相等；
   （因为root走到所有叶子节点都是0，而走到u下面的叶子节点必然经过u，所以边都得相等）；
   而对于其他的边我们可以任意赋值，因为假设异或到u时值为w，那我们到u的叶子节点的那条边赋值为w就行；
   所以 max = (n−1) − (f(u)-1);（其中f(u)是u向下直接连接的叶子节点数量）;

那么为什么这样构造树中任意两点距离异或值都为0？其实就是上面的证明了。

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
#include <random>
#include<bitset>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define dre(x) scanf("%lf",&x)
#define ddre(a,b) scanf("%lf %lf",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
//#define int long long
// #define double long double
// typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 5e5 + 7;
const int M = 5e5 + 7;
const int mod = 19980829;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

vector<int> v[maxn];
int dep[maxn];
int cnt[maxn];

void dfs(int u,int fa)
{
	for(auto x : v[u])
	{
		if(x == fa) continue;
		dep[x] = dep[u] + 1;
		dfs(x,u);
	}
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	int a,b;
    	cin>>a>>b;
    	
    	v[a].push_back(b);
    	v[b].push_back(a);
	}
    
    int root = -1;
    for(int i=1;i<=n;i++)
    	if(v[i].size() == 1)
		{
			root = i;
			cnt[v[i][0]] ++;
		}
    
    dfs(root,-1);
    
    int mx = n-1;
    int mn = 1;
    for(int i=1;i<=n;i++)
	{
		if(v[i].size() == 1 && ((dep[i] - dep[root]) & 1)) mn = 3;
		
		if(cnt[i] >= 2) mx -= (cnt[i] - 1);
	}
	
	cout<<mn<<' '<<mx<<'\n';    
}

int main()
{
	IOS;
	
	int t;
//	ire(t);
//	cin>>t;
	t = 1;
	while(t--)
	{
		solve();
	}
    	
 	return 0;
}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129