美团笔试——遍历

using namespace std;
int fa[MAXN], mincost[MAXN];
vector<int>edge[MAXN];
priority_queue<int>cost[MAXN];
int n, m, dep;
void init() {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
mincost[i] = n;
edge[i].clear();
while (!cost[i].empty()) cost[i].pop();
}
dep = 0;
}
void dfs(int u, int depp) {
if (edge[u].size() == 0) {
dep = max(dep, depp);
cost[u].push(0);
return;
}
int val = 0;
for (int i = 0; i < edge[u].size(); ++i) {
dfs(edge[u][i], depp + 1);
while (!cost[edge[u][i]].empty()) {
val += cost[edge[u][i]].top();
val += 2;
cost[edge[u][i]].pop();
}
}
//cout << "u & val: " << u << " " << val << endl;
cost[u].push(val);
}
void find_max_dep(int u) {

}
int find_fa(int x) {
if (fa[x] == x) {
return x;
}
else {
return find_fa(fa[x]);
}
}
int main() {
while (~scanf("%d", &n)) {
init();
int st, ed;
m = n - 1;
for (int i = 0; i < m; ++i) {
scanf("%d %d", &st, &ed);
edge[st].push_back(ed);
fa[ed] = st;
}
for (int i = 1; i <= n; ++i) {
find_fa(i);
}
int rt;
for (int i = 1; i <= n; ++i) {
if (fa[i] == i) {
rt = i;
break;
}
}
//printf("rt: %d\n", rt);

dfs(rt, 0);
//cout << dep << endl;
int ans = 0;
bool flag = false;
while (!cost[rt].empty()) {
ans += cost[rt].top();
//cout << cost[rt].top() << endl;
cost[rt].pop();
}
ans -= dep;
printf("%d\n", ans);
}
return 0;
}
#美团#