Zoom 8.10 笔试分享

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<int> mp[N];
int cred[N], cblue[N], n;
string color;
ll ans;
void dfs(int u,int fa){
    cred[u] = cred[fa];
    cblue[u] = cblue[fa];
    if(color[u] == 'R'){
        cred[u]++;
    }else{
        cblue[u]++;
    }
    // cout<<u<<" "<<cred[u]<<" "<<cblue[u]<<endl;
    ans += abs(cred[u] - cblue[u]);
    for(auto v:mp[u]){
        if(v == fa) continue;
        dfs(v, u);
    }
    return;
}
int main() {
    cin >> n >> color;
    color = " "+color;
    for (int i = 0, u, v; i < n - 1; i++) {
        cin >> u >> v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans<<endl;
}

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int tot, ptot;
map<string, int> name;// 公司name
map<string, int> pname;// 人name
map<int, int> mp;
int fa[N], sz[N];
int getfa(int u){
    return fa[u] != u ? fa[u] = getfa(fa[u]) : u;
}
void join(int u,int v){
    int f1 = getfa(u), f2 = getfa(v);
    if(f1 != f2){
        fa[f2] = fa[f1];
        sz[f1] += sz[f2];
        sz[f2] = 0;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int q;
    cin >> q;
    int type, m;
    string in, bu;
    tot = q;
    for(int i = 1; i <= q; i++){
        cin >> type;
        if(type == 1){
            cin >> in >> m;
            int thisroot = i;
            pname[in] = thisroot;
            fa[thisroot] = thisroot;
            sz[thisroot] = 0;
            vector<int> tonari;
            
            for(int i = 0; i < m; i++){
                cin >> bu;
                if(name.find(bu) == name.end()){
                    name[bu] = ++tot;
                    fa[name[bu]] = name[bu];
                    sz[name[bu]] = 1;
                }
                tonari.push_back(name[bu]);
                join(thisroot, name[bu]);
            }
            mp[thisroot] = tonari.size();
        }else{
            cin >> in;
            if(pname.find(in) == pname.end()){
                cout<<"error\n";
                continue;
            }
            int pid = pname[in];
            int total = sz[getfa(pid)];
            int tonari = mp[pid];
            cout<<total - tonari<<"\n";
        }
    }
}
/*
5
1 Alice 2
Zoom Apple
2 Bob
2 Alice
1 Bob 2
Apple Microsoft
2 Bob
*/