A. Y 树

题目描述

kjhkjki 得到了一棵 \(n\) 个点的树。现在他想知道，这棵树中有多少组无序三元组 \((a, b, c)\) (\(a < b < c\)) 构成 Y 结构。即三个点均不在另外两点的最短路径上。

输入格式

第一行一个整数 \(n\)，表示节点数。

接下来 \(n - 1\) 行，每行两个整数 \(u, v\)，表示一条边。

保证输入是一棵树。

输出格式

一行一个整数，表示答案。

样例

输入样例1

1
2
3
4
5
5
1 2
2 3
2 4
1 5

输出样例1

1
2

输入样例2

1
2
3
4
5
6
6
1 2
2 3
3 4
4 5
5 6

输出样例2

1
0

输入样例3

1
2
3
4
5
6
7
8
9
10
11
12
12
1 6
3 4
10 4
5 9
3 1
2 3
7 2
2 12
1 5
6 8
4 11

输出样例3

1
91

数据范围与提示

\(1 \leq n \leq 10^6\)

思路与题解

设树的总结点数为 \(n\) ，等价于求出所有 \(a, b, c\) 三点在彼此路径上的三元组数 \(x\)，然后答案为 \(C^3_n - x\)

对于 \(x\) 假设去掉某个节点 \(u\) ，树被分成了若干连通块，设这些连通块的节点数分别为 \(s_1, s_2, \ldots, s_k\) ，则 等价于求任取两个不在统一连通块的节点对 \((a, b)\) ，\(c\) 即为选取的 \(u\)

再反过来考虑，等价于 \(C^2_{n-1}\) 减去每个连通块内的节点对数之和，即

\[C^2_{n-1}-\sum_{i=1}^k C^2_{s_i}\]

所以只用求出每个连通块的节点数即可，由于这又是一颗树，也就是求每个节点的子树大小，父亲那一分支 \(s_k\) 即为 \(n-1-\sum_{i=1}^{k-1}s_i\)

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
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n-1; ++i) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }

    vector<int> pa(n, -1), order; // order 存储遍历顺序
    vector<vector<int>> child(n);

    stack<pair<int, int>> s;
    s.emplace(0, -1);
    while (!s.empty()) {
        auto [u, p] = s.top(); s.pop();
        order.emplace_back(u);
        for (auto v : adj[u]) {
            if (v == p) continue;
            pa[v] = u;
            child[u].emplace_back(v);
            s.emplace(v, u);
        }
    }

    // 求子树大小
    vector<ll> subtree(n, 1);
    for (int i = (int)order.size() - 1; i >= 0; --i) {
        int u = order[i];
        int p = pa[u];
        if (p >= 0) subtree[p] += subtree[u];
    }
    
    // 每一个连通块的贡献，所有孩子的子树个数 + 父亲的连通分支的贡献
    vector<ll> vCon(n, 0);
    ll base = (ll)(n-1) * (n-2) / 2;
    for(int i = 0; i < n; ++i){
        int u = i;
        ll bCon = n-1;
        for(auto v : child[u]){
            vCon[u] += sunbtree[v] * (subtree[v] - 1) / 2;
            bCon -= subtree[v];
        }
        if(bCon > 0) {
            vCon[u] += bCon * (bCon - 1) / 2;
        }
        vCon[u] = base - vCon[u];
    }
    
    ll ans = (ll)n * (n-1) * (n-2) / 6;
    for(int i = 0; i < n; ++i){    
        ans -= vCon[i];
    }
    cout << ans;
    
    return 0;
}

B. 树的重心

题目描述

树的重心被定义为：树中的一个节点，删除该点后，使得形成的多棵树中节点数最大的树的节点数最小。求树的重心。

Format

Input

第一行包含一个整数 \(n\)，表示树节点的个数。

接下来 \(n - 1\) 行，每行两个数，表示一条边的两个节点。

节点编号从 1 到 \(n\)。

Output

输出树的重心。如果有多个重心，则按编号从小到大依次输出。

Samples

输入样例

1
2
3
4
5
6
6
1 2
2 3
2 5
3 4
3 6

输出样例

1
2 3

Limitation

\(1 \leq n \leq 5 \times 10^4\)

思路与题解

经典题目，求出每个节点的子树大小，然后对于每个节点，求出删除该节点后，剩余各个连通块的大小，取最大值，最后取最小值对应的节点即可

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
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for(int i = 0; i < n-1; ++i){
        int x,y;
        cin >> x >> y;
        x--; y--;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }

    vector<int> pa(n, -1), order;
    vector<vector<int>> child(n);

    stack<pair<int, int>> s;
    s.emplace(0, -1);
    while(!s.empty()){
        auto [u, p] = s.top();
        s.pop();
        order.emplace_back(u);
        for(auto v : adj[u]){
            if(v == p) continue;
            pa[v] = u;
            child[u].emplace_back(v);
            s.emplace(v, u);
        }
    }

    vector<int> ans;
    vector<int> subtree(n, 1);
    for(int i = order.size()- 1; i >= 0;--i){
        int u = order[i];
        int p = pa[u];
        if(p >= 0) subtree[p] += subtree[u];
    }

    int minSize = n;
    vector<int> weight(n, 0);
    for(int i = 0; i < n; ++i){
        int u = i;
        int maxPart = n - subtree[u]; // 父亲的连通块
        for(auto v : child[u]){
            if(subtree[v] > maxPart){
                maxPart = subtree[v];
            }
        }
        weight[i] = maxPart;
    }
    for (int i = 0; i < n; ++i) {
        if (weight[i] < minSize) {
            minSize = weight[i];
            ans = {i + 1};
        } else if (weight[i] == minSize) {
            ans.emplace_back(i + 1);
        }
    }
    sort(ans.begin(), ans.end());
    for(auto v : ans){
        cout << v << " ";
    }
    return 0;
}

C. 有多远？

传统题 1000ms 256MB

Description

村子里有 \(n\) 座房子，一些双向的道路把它们连接起来。

每天人们都喜欢问这样的问题：“从 A 家到 B 家要去多远？”

神奇的是，在这个村子里，答案总是独特的，因为每两幢房子之间都有只有一条简单路径（“简单”的意思是你不能两次去一个地方）。你的任务就是回答所有这些好奇的人。

Format

Input

在第一行中有两个数字 \(n\) 和 \(m\) 表示房子的数量和查询的数量。

接下来下面 \(n-1\) 行，每一行由三个数字 \(x, y, c\) 组成，用一个空格隔开，表示有一条路连接 \(x\) 和 \(y\) 家，长度为 \(c\)。房子的标号从 1 到 \(n\)。

接下来的 \(m\) 行每一行都有不同的整数 \(a\) 和 \(b\)，你要回答房子 \(a\) 和房子 \(b\) 之间的距离。

Output

输出 \(m\) 行，每行一个整数，表示每个查询的答案。

Samples

输入样例 1

1
2
3
4
5
3 2
1 2 10
3 1 15
1 2
2 3

输出样例 1

1
2
10
25

输入样例 2

1
2
3
4
2 2
1 2 100
1 2
2 1

输出样例 2

1
2
100
100

Limitation

\(1 \leq n \leq 40000\), \(1 \leq m \leq 200\), \(1 \leq c \leq 40000\)

思路与题解

求 LCA 即可，这里采用倍增法

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
#incldue <bits/stdc++.h>

using namespace std;
using ll = long long;

int n,m;
int LOG = 1;
vector<vector<int>> up;
vector<vector<pair<int, int>>> g; // node list
vector<int> depth;
vector<ll> dist;

int lca(int, a, int b){
    if(depth[a] < depth[b]) swap(a, b);
    int diff = depth[a] - depth[b];
    for(int k = 0; k < LOG; ++k){
        if(diff & (1 << k)) a = up[k][a];
    }
    if(a == b) return a;
    for(int k = LOG - 1; k >= 0; --k){
        if(up[a][k] != up[b][k]){
            a = up[k][a];
            b = up[k][b];
        }
    }
    return up[0][a];
}

int main(){
    cin >> n >> m;
    grid.resize(n);
    for(int i = 0; i < n-1; ++i){
        int x,y,z;
        cin >> x >> y >> z;
        x--; y--;        
        grid[x].emplace_back(y, z); 
        grid[y].emplace_back(x, z);        
    }
    while((1 << LOG) <= n) LOG++;
    up.assign(LOG, vector<int>(n, -1));    
    depth.assign(n, 0);
    dist.assign(n, 0);    
    
    stack<pair<int, int>> s;
    s.emplace(0, -1);
    
    up[0][0] = 0;
    depth[0] = 0;
    dist[0] = 0;    
    
    while(!s.empty()){
        auto [u, p] = s.top();
        s.pop();
        for(auto [v, w] : grid[u]){
            if(v == p) continue;
            up[0][v] = u;
            depth[v] = depth[u] + 1;
            dist[v] = dist[u] + w;
            s.emplace(v, u);
        }
    }
    
    for(int i = 0; i < LOG; ++i){
        for(int v = 0; v < n;++v){
            int mid = up[i-1][v];
            up[i][v] = (mid == -1 ? -1 : up[k-1][mid]);
        }
    }
    
    while(m--){
        int u,v;
        cin >> u >> v;
        u--; v--;
        int w = lca(u, v);
        ll ans = dist[u] + dist[v] - 2 * dist[w];
        cout << ans << "\n";        
    }
    
    return 0;
}

D. Phone List

Description

给定 \(n\) 个长度不超过 10 的数字串，问其中是否存在两个数字串 \(S, T\)，使得 \(S\) 是 \(T\) 的前缀，多组数据。

输入格式

第一行一个整数 \(T\)，表示数据组数。

对于每组数据，第一行一个数 \(n\)，接下来 \(n\) 行输入 \(n\) 个数字串。

输出格式

对于每组数据，若存在两个数字串 \(S, T\)，使得 \(S\) 是 \(T\) 的前缀，则输出 \(NO\)，否则输出 \(YES\)。

请注意此处结果与输出的对应关系！

Samples

输入数据 1

1
2
3
4
5
6
7
8
9
10
11
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

输出数据 1

1
2
No
YES

Limitation

对于 100% 的数据，\(1 \leq T \leq 40, 1 \leq n \leq 10^4\)

思路与题解

前缀树，当插入一个新字符串时，如果终止的地方已经是一个终止节点，说明存在前缀，如果插入过程中遇到一个终止节点，说明存在前缀

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
#include <bits/stdc++.h>

using namespace std;

class trie{
    int cnt = 0;
    struct Node{
        int next[10]{};
        bool exist;
        Node(){
            fill(next, next+10, -1);    
            exist = false;
        }
    };
    
    vector<Node> nodes;
    
    public:
    trie(){
        nodes.emplace_back();
    }    
    ~trie() = default;
    
    bool insert(string s);
    int cur = 0;
    int n = s.size();
    for(int i = 0; i < n; ++i){
        int c = s[i] - '0';
        if(nodes[cur].next[c] == -1){
            nodes[cur].next[c] = ++cnt;
            nodes.emplace_back();
        }
        cur = nodes[cur].next[c];
        if(nodes[cur].exist) return true; // 已经存在前缀
    }
    
    for(int k : nodes[cur].next){
        if(k != -1) return true; // 当前字符串是前缀
    }    
    nodes[cur].exist = true;
	return false;
};

int solve(){
    int n;
    cin >> n;    
    trie tr;
    while(n--){
        string s;
        cin >> s;
        if(!yes) yes = tr.insert(s);
    }
    cout << (yes ? "NO\n" : "YES\n");
}

int main(){
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

E. 访问所有节点的最小电费

Background

SDZX 是一棵树。

QiangBro 开着小卡丁车在校园里转悠。

Description

SDZX 可以看作是一棵树，他有 \(n\) 个结点，有 \(n-1\) 条边将他们相连。QiangBro 开着卡丁车，想把每个结点都访问至少一次，但是他每经过一条边，都会消耗1块钱的电费！

请为他规划起点和开车的路线，使得拜访每个结点至少一次，且消耗尽可能少的电。

输出他最少需消耗的电费。

Format

Input

第一行，一个正整数 \(n\)。

接下来 \(n-1\) 行，每行两个整数 \(u, v\)，表示结点 \(u, v\) 之间存在一条边将他们相连。

保证给出的边构成一棵合法的树。

Output

输出一行，一个整数，最少的电费开销！

Samples

输入数据

1
2
3
4
5
5
1 2
1 3
1 4
1 5

输出数据

1
8

Limitation

\(1 \leq n \leq 10^5\)

思路与题解

等价于求树的直径，答案为 \(2(n-1) - d\)，其中 \(d\) 为树的直径

原因是从任意节点出发，走完所有边需要 \(2(n-1)\)，但是可以通过走直径路径来节省 \(d\) 的路程

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
#include <bits/stdc++.h>

using namespace std;

int n, c = 0;
vector<vector<int>> adj;
vector<int> d;

void dfs(int u, int p){
    for(auto v : adj[v]){
        if(v == p) continue;
        d[v] = d[u] + 1;
        if(d[v] > d[c]) c = v;
        dfs(v, u);
    }
}

int main(){
    cin >> n;
    adj.assign(n, {});
    d.assign(n, 0);
    for(int i = 0; i < n-1; ++i){
        int x,y;
        cin >> x >> y;
        x--; y--;
        adj[x].emplace_back(y);        
        adj[y].emplace_back(x); 
    }
    
    d[0] = 0;
    dfs(0, -1);
    
    fill(d.begin(), d.end(), 0);
    d[c] = 0;
    dfs(c, -1);
    
    cout << 2 * (n - 1) - d[c];
    return 0; 
}
On this page41
数据结构作业题解08
  1. A. Y 树
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 数据范围与提示
    6. 思路与题解
  2. B. 树的重心
    1. 题目描述
    2. Format
      1. Input
      2. Output
    3. Samples
    4. Limitation
    5. 思路与题解
  3. C. 有多远？
    1. Description
    2. Format
      1. Input
      2. Output
    3. Samples
    4. Limitation
    5. 思路与题解
  4. D. Phone List
    1. Description
    2. 输入格式
    3. 输出格式
    4. Samples
      1. 输入数据 1
      2. 输出数据 1
    5. Limitation
    6. 思路与题解
  5. E. 访问所有节点的最小电费
    1. Background
    2. Description
    3. Format
      1. Input
      2. Output
    4. Samples
    5. Limitation
    6. 思路与题解