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;
} 