【备战秋招】每日一题:2023.3.5-米哈游笔试-最长的通讯路径

作者：很楠不爱3 | 2024-03-09 10:46:30

踩

最长的通讯路径

为了更好的阅读体检，可以查看我的算法学习网
 在线评测链接:P1065

题目内容

塔子哥是一位研究者，他在研究网络传输时遇到了一个问题。

他拿到了一张通讯网络的拓扑结构图，其中每条通讯线路被染成了红色或者蓝色。

他想找到一条长度最长的通讯路径，使得路径上相邻的两条线路颜色不同。

输入描述

第一行输入一个正整数 $n$ ，代表节点数量。

接下来的 $n - 1$ 行，每行输入两个正整数 $u, v$ 和一个字符 $c h r$ ，代表节点 $u$ 和节点 $v$ 有一条边连接。

若为 $^{'} R^{'}$ 代表这条边是红色， $^{'} B^{'}$ 代表这条边是蓝色。

$1\le n \le 10^5$

$1\le u,v\le n$

保证输入的是一颗树。

输出描述

一个正整数，代表塔子哥可以选择的路径最大长度。

样例

输入

输出

2
1

样例解释

选择 $1 - 2 - 3$ 的路径即可。

思路

默认以1为根节点进行 $df s$ 遍历。

$d p [i] [0]$ 表示在以 $i$ 为根节点的子树中，且与 $i$ 的连边为蓝色所有路径中最长的。 $d p [i] [1]$ 表示以 $i$ 为根节点的子树中，与 $i$ 的连边为红色的所有路径中最长的。那从前面两个 $d p$ 我们可以知道以 $i$ 为根节点，且选择了节点 $i$ 的最长路径肯定是 $d p [i] [0] + d p [i] [1]$ 。那假如我们讨论了所有子树，那么最长路径也肯定知道了。

现在问题在于如何得到所有节点的 $d p$ 值呢。我们发现假如我们知道了一个节点u的所有子节点 $v$ 的 $d p$ 值，那么 $u$ 的 $d p$ 值也就知道了。因为节点 $u$ 的 $dp[u][x]=max(dp[v][x\oplus 1]+1)$ .所以我们需要先知道所有子节点的 $d p$ 值，再用子节点的 $d p$ 值去更新父节点。这个我们用 $df s$ 去处理。

代码

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef pair<int, int>pii;
int n;
vector<pii>edge[MAXN];
int dp[MAXN][2];
int maxn = 0;
void dfs(int u, int fa){
	if(edge[u].size() == 1 && edge[u][0].first == fa)return;//叶子节点直接return，因为叶子节点的两个dp值肯定是0
	for(int i = 0; i < edge[u].size(); i++){
		pii now = edge[u][i];
		int v = now.first;
		if(v == fa)continue;//如果是父节点，continue，因为我们讨论的是以u为根节点的子树，而u的父节点肯定不属于这颗子树的
		dfs(v, u);//得到子节点答案
		int col = now.second;
		dp[u][col] = max(dp[u][col], dp[v][col ^ 1] + 1);//dp状态转移，用子节点v更新u
		maxn = max(maxn, dp[u][0] + dp[u][1]);//记录答案
	}
}
int main(){
	cin >> n;
	int u, v;
	char ch;
	memset(dp, 0, sizeof dp);//dp初始化
	for(int i = 1; i <= n - 1; i++){
		scanf("%d%d", &u, &v);
		cin >> ch;
		edge[u].push_back({v, ch == 'R'?1:0});
		edge[v].push_back({u, ch == 'R'?1:0});//建图
	}
	dfs(1, 0);
	cout << maxn << endl;
}
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

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class TreeNode{
    List<TreeNode> friends;
    List<Character> colors;

    public TreeNode(){
        friends = new ArrayList<TreeNode>();
        colors = new ArrayList<Character>();
    }
}

public class Main {

//    static int result = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        TreeNode[] tree = new TreeNode[n];
        for(int i = 0; i < n; i++) tree[i] = new TreeNode();
        for(int i=0;i<n-1;i++){
            String[] s = in.nextLine().split(" ");
            int x = Integer.parseInt(s[0])-1;
            int y = Integer.parseInt(s[1])-1;
            char c = s[2].charAt(0);
            if(x>y){
                int temp = x;
                x = y;
                y = temp;
            }
            tree[x].friends.add(tree[y]);
            tree[x].colors.add(c);
            tree[y].friends.add(tree[x]);
            tree[y].colors.add(c);
        }
//        dfs2(tree[0], null);
//        System.out.println(result);
        int result = 0;
        for(int i=0;i<n;i++){
            result = Math.max(result, dfs(tree[i], null, 'B'));
            result = Math.max(result, dfs(tree[i], null, 'R'));

        }
        System.out.println(result);

    }

//    public static void dfs2(TreeNode tree, TreeNode parent){
//        if(tree==null) return;
        int result = 0;
//        for(int i=0;i<tree.friends.size();i++){
//            if(tree.friends.get(i)==parent) continue;
//            if(tree.colors.get(i)=='R')
//                result = Math.max(result,dfs(tree.friends.get(i),tree,'B')+1);
//            else
//                result = Math.max(result,dfs(tree.friends.get(i),tree,'R')+1);
//            dfs2(tree.friends.get(i),tree);
//        }
//    }

    public static int dfs(TreeNode tree, TreeNode parent, char color){
        if(tree==null) return 0;
        int res = 0;
        for(int i=0;i<tree.friends.size();i++){
            if(tree.friends.get(i)==parent) continue;
            if(tree.colors.get(i)==color) {
                if(color=='R')
                    res = Math.max(res,dfs(tree.friends.get(i),tree,'B')+1);
                else
                    res = Math.max(res,dfs(tree.friends.get(i),tree,'R')+1);
            }
        }
        return res;
    }

}
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

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const lines = [];

(async () => {
    for await (const line of rl) {
        lines.push(line);
    }
    const n = parseInt(lines[0]);
    const edges = [[]];
    // construct the graph
    for (let i = 1; i < lines.length; i++) {
        const [u, v, color] = lines[i].split(' ');
        if (!Array.isArray(edges[parseInt(u)])) {
            edges[parseInt(u)] = [];
        }
        edges[parseInt(u)].push([parseInt(v), color === 'R' ? 0 : 1]);
        if (!Array.isArray( edges[parseInt(v)])) {
            edges[parseInt(v)] = [];
        }
        edges[parseInt(v)].push([parseInt(u), color === 'R' ? 0 : 1]);
    }
    // process the problem
    const dp = new Array(n + 1).fill([]).map(i => [0, 0]);
    let res = -Infinity;
    // dfs
    const dfs = (node, father) => {
        // is leaf node
        if (edges[node].length === 1 && edges[node][0][0] === father) {
            return;
        }

        // traverse every child node
        for (let i = 0; i < edges[node].length; i++) {
            const cur = edges[node][i][0];
            const color = edges[node][i][1];
            if (cur === father) {
                continue;
            }
            dfs(cur, node);
            dp[node][color] = Math.max(dp[node][color], dp[cur][color ^ 1] + 1);
        }
        res = Math.max(res, dp[node][0] + dp[node][1]);
    }

    dfs(1, 0);

    console.log(res);
})();
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

python

from collections import defaultdict

MAXN = 200005
n = 0
edge = defaultdict(list)
dp = [[0] * 2 for _ in range(MAXN)]
maxn = 0


def dfs(u, fa):
    global maxn
    if len(edge[u]) == 1 and edge[u][0][0] == fa:
        return

    for now in edge[u]:
        v = now[0]
        if v == fa:
            continue
        dfs(v, u)
        col = now[1]
        dp[u][col] = max(dp[u][col], dp[v][col ^ 1] + 1)
        maxn = max(maxn, dp[u][0] + dp[u][1])


def main():
    global n
    n = int(input())
    for _ in range(n - 1):
        u, v, ch = input().split()
        u, v = int(u), int(v)
        edge[u].append((v, 1 if ch == 'R' else 0))
        edge[v].append((u, 1 if ch == 'R' else 0))

    dfs(1, 0)
    print(maxn)


if __name__ == "__main__":
    main()
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

题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册
用户名: 塔子哥学算法) 进行删除。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/214780