Edge Weight Assignment

发表于 分类于 ，

    给定一棵 $n$ 个点的无根树，要求给每条边分配一个正整数权值，使得任意两个叶子节点之间路径上的边权异或值为 $0$。求最少要多少种不同权值，以及最多可以使用多少种不同权值。

    这里，填入的边权值可以为任意大。

    $3 \le n\le 10^5$

Edge Weight Assignment

Created by LXC on Tue Feb 27 10:44:04 2024

https://codeforces.com/problemset/problem/1338/B

ranting: 1800

tag: bitmasks, constructive algorithms, dfs and similar, greedy, math, trees

problem

给定一棵 $n$ 个点的无根树，要求给每条边分配一个正整数权值，使得任意两个叶子节点之间路径上的边权异或值为 $0$。求最少要多少种不同权值，以及最多可以使用多少种不同权值。
这里，填入的边权值可以为任意大。

$3 \le n\le 10^5$

solution

对于不同权值总数最小化，考虑任意叶子节点之间的距离，如果全都是偶数那么只需要一种权值，否则至少需要三种权值。只需判断叶子节点之间的距离的奇偶性。可以从一个叶子开始搜索到其他叶子不存在奇数距离，那么其他叶子之间距离也不是奇数。

对于不同权值总数最大化，考虑只经过两条边的叶子对。这种叶子对经过的两条边权值必须相等，而其他边权总有赋值为不同值而路径异或和为0的情况。

code

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

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<vector<int>> g(n+1);
    for (int i=1; i<n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int even = 1;
    function<void(int, int, int)> dfs = [&](int u, int fa, int stp) {
        int c = 0;
        for (int v:g[u]) {
            if (v == fa) continue;
            c++;
            dfs(v, u, stp+1);
        }
        if (c == 0 && stp%2 == 1) even = 0;
    };
    for (int i=1; i<=n; i++) {
        if (g[i].size() == 1) {
            dfs(i, 0, 0);
            break;
        }
    }
    cout << (even?1:3) << " ";
    vector<int> cnt(n+1);
    for (int i=1; i<=n; i++) {
        if (g[i].size() == 1) cnt[g[i][0]]++;
    }
    int ans = n-1;
    for (int i=1; i<=n; i++) {
        ans -= max(0, cnt[i]-1);
    }
    cout << ans << "\n";

}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}