❄️题目描述

Monica拿到了一棵有根树，根结点为1号节点。每个节点被染成红色或者蓝色。
假设第 $i$ 个节点的权值 $a_i$ 定义为：从根结点出发到该节点的路径上，红色节点和蓝色节点的数量之差。请你帮Monica计算出所有节点的权值之和。

输入描述

第一行输入一个正整数 $n$，代表节点的数量。
第二行输入一个长度为 $n$， 的字符串，字符‘R’代表第 i 个节点被染成红色， ‘B’为蓝色。
接下来的 $n-1$ 行，每行输入两个正整数 $u$ 和 $v$，代表节点 $u$ 和节点 $v$ 有一条路径连接，
$1\le n\le 10^5$

输出描述

所有节点权值之和

示例

输入

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

输出

3
1

说明

结构如上图
1节点本身就是根结点，红蓝数量差为1，权值为1。
从根到4节点和5节点红蓝数量差为0，权值为0。
从根到2节点红蓝数量差为1，权值为1。

分析

可见，权值就是红蓝数量差的绝对值，权值永远 $\ge$ 0 。
 

Node 节点

struct Node {
  int color; // 颜色
  vector<int> cons; // 有连接的的节点
  bool visited = false; // 访问位
};
1
2
3
4
5

如上的结构体可以节省空间，也能缩短遍历的时间。

就是一个简单的DFS

#include 
#include 
#include 
#include 

using namespace std;

struct Node {
    int color; // 颜色
    vector<int> cons; // 有连接的的节点
    bool visited = false; // 访问位
};

long long ans = 0; // 最终结果

void dfs(Node nodes[], int n, int last_ans) {
    last_ans += nodes[n].color; // 上一个节点的权值
    nodes[n].visited = true; // 访问过了
    ans += abs(last_ans); // 加上绝对值
    if (nodes[n].cons.size() != 0) { // 有没有和当前节点连接的节点
        for(int i = 0; i < nodes[n].cons.size(); i++) {
            if (!nodes[nodes[n].cons[i]].visited) // 要是没访问我就访问
                dfs(nodes, nodes[n].cons[i], last_ans);
        }
    }
    return;
}

int main(){
    Node nodes[100000] = {};
    int n;
    cin >> n;
    string colors;
    cin >> colors;

    for(int i = 0; i < n; i++)
        nodes[i].color = colors[i]=='R' ? -1 : 1; // 红色: -1, 蓝色: 1
    
    for(int i = 0; i < n - 1; i++) {
        int l, r;
        cin >> l >> r;
        nodes[l - 1].cons.push_back(r - 1); // 连线双方都要添加到彼此的cons中
        nodes[r - 1].cons.push_back(l - 1);
    }

    dfs(nodes, 0, 0);
    cout << ans;
    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