Programming Competition

发表于 更新于 分类于 ，

    给定 $n$ 个点的树，问能选出多少点对 $(u,v)$，满足 $u,v$ 互相不为祖先，每个点只能被包含在一个点对中。

Programming Competition

Created by LXC on Sun Feb 25 18:02:08 2024

https://codeforces.com/problemset/problem/1914/F

ranting: 1900

tag: dfs and similar, dp, graph matchings, greedy, trees

problem

给定 $n$ 个点的树，问能选出多少点对 $(u,v)$，满足 $u,v$ 互相不为祖先，每个点只能被包含在一个点对中。

solution

定义$f_i$为i子树中能选取出符合条件的点对数。$s_i$是i子树的节点个数。

对于i子树中，设共有k个儿子，按照子树节点个数由大到小排序第j个儿子为$son_{i,j}$

当$s_{son_{i,1}} < s_{son_{i,2}}+\cdots + s_{son_{i,k}}$，所有的$s_x-1$个节点将都会成对，对于若为奇数则多一个1，这种情况下$f_i = \lfloor\frac{s_x-1}{2}\rfloor$

当$s_{son_{i,1}} \ge s_{son_{i,2}}+\cdots + s_{son_{i,k}}$，首先形成$\sum
\limits_{j=2}^k s_{son_{i,j}}$对节点，$son_{i,1}$中剩余的未匹配节点有$s_{son_{i,1}}-\sum
\limits_{j=2}^k s_{son_{i,j}}$，这些节点我们尽量用$f_{son_{i,1}}$的点对保留，这样可以形成更多的点对。这种情况下$f_i = \sum
\limits_{j=2}^k s_{son_{i,j}} + \lfloor\frac{ \min \lbrace s_{son_{i,1}}-\sum
\limits_{j=2}^k s_{son_{i,j}}, 2f_{son_{i,1}}\rbrace }{2}\rfloor$

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
80

#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=2; i<=n; i++) {
        int x;
        cin >> x;
        g[x].push_back(i);
    }
    vector<ll> son(n+1);
    function<ll(int)> dfs1 = [&](int x) {
        son[x] = 1;
        for (auto y:g[x]) {
            son[x] += dfs1(y);
        }
        return son[x];
    };
    dfs1(1);
    function<ll(int)> dfs2 = [&](int x)->ll { // x子树中匹配最多的个数。
        ll s = 0, mx = 0, u = 0;
        for (auto y:g[x]) {
            s += son[y];
            if (son[y] > mx) {
                mx = son[y];
                u = dfs2(y);
            } else if (son[y] == mx) {
                u = max(u, dfs2(y));
            }
        }
        ll ans = 0;
        // mx <= s - mx 可以全部匹配，奇数剩一个 
        if (2*mx <= s) {
            return (son[x]-1)/2; //下取整
        } else {
            return s - mx + min(u*2, 2*mx-s)/2; // mx - (s - mx) 不能被其他子树匹配的点，内部消化。
        }
    };
    cout << dfs2(1) << "\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;
}