8.10 zoom 笔试题解心得

T1 求树的权值

告诉你一棵树的结点分为蓝色和红色，一个结点的权值定义为：从根结点到该结点路径上的红蓝结点个数之差的绝对值。

求整棵树的权值之和。

#include <bits/stdc++.h>

using namespace std;

int n; 
string color;
vector<vector<int>> g;
long long ans = 0;

void dfs(int x, int bl, int red, int from) {
    if (color[x] == 'R') ++red;
    else ++bl;
    ans += abs(bl-red);
    for (auto to : g[x]) {
        if (to != from) {
            dfs(to, bl, red, x);
        }
    }
}

int main() {
    cin >> n;
    cin >> color;
    g.resize(n);
    int u, v;
    for (int i = 0; i < n-1; ++i) {
        cin >> u >> v;
        g[u-1].push_back(v-1);
        g[v-1].push_back(u-1);
    }
    dfs(0, 0, 0, 0);
    cout << ans << endl;
    return 0;
}

T2 给用户推荐股票的数目

每个用户都有喜欢的股票，如果一个用户 A 喜欢股票 a, b；用户 B 喜欢 b, c。那么相当于在股票 a 和 b, b 和 c 之间建立了两条边，如果用户 C 喜欢 c，那么系统会给 c 推荐股票 a 和 b。

求给用户 x 推荐股票的数目（不包含自己喜欢的股票）

#include <bits/stdc++.h>

using namespace std;

#define maxn 50005

struct UF {
    int f[maxn+5], cnt[maxn+5];

    UF(int n) {
        for (int i = 0; i <=n; ++i) {
            f[i] = i; cnt[i] = 1;
        }
    }
    int getp(int x) { return f[x] == x ? f[x] : f[x] = getp(f[x]); }
    void add(int x, int y) {
        int px = getp(x), py = getp(y);
        if (cnt[px] < cnt[py]) swap(px, py);
        if (px != py) {
            f[px] = py;
            cnt[py] += cnt[px];
        }
    }
};

int main() {
    int q; cin >> q;
    int n, op, no = 0;
    string name, share;
    unordered_map<string, set<int>> users;
    unordered_map<string, int> shareid;
    UF uf(maxn);
    while (q--) {
        cin >> op >> name;
        if (op == 1) {
            cin >> n;
            vector<int> ids(n);
            for (int i = 0; i < n; ++i) {
                cin >> share;
                if (!shareid.count(share)) shareid[share] = no++;
                ids[i] = shareid[share];
                users[name].insert(ids[i]);
            }
            for (int i = 0; i < n; ++i) {
                for (int j = i+1; j < n; ++j) {
                    uf.add(ids[i], ids[j]);
                }
            }
        } else {
            if (users[name].empty()) {
                cout << "error" << endl;
                continue;
            }
            int inc = 0;
            set<int> pp;
            for (auto us : users[name]) {
                int p = uf.getp(us);
                if (pp.count(p)) continue;
                pp.insert(p);
                auto cnt = uf.cnt[p];
                inc += cnt;
                for (auto us2 : users[name]) {
                    if (uf.getp(us) == uf.getp(us2)) --inc;
                }
            }
            cout << inc << endl;
        }
    }
    return 0;
}

#校招##做完zoom2023秋招笔试，人麻了#