Zoom 8.10 笔试分享
1.
#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;
} 2. #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
*/ 
