关注
#include <bits/stdc++.h>
#include <stdio.h>
#define N 100005
using namespace std;
struct edge
{
int from;
int to;
edge(int i=0,int j=0)
{
from = i;to = j;
}
};
vector<edge>mp;
int visit[N];
int num[N];
int depth = 1;
int maxdepth = 1;
int cmp(edge l,edge r)
{
return l.from < r.from;
}
void dfs(int from)
{
edge tmp(from,0);
depth++;
maxdepth = max(maxdepth,depth);
auto pos = lower_bound(mp.begin(),mp.end(),tmp,cmp);
for(auto it=pos;it!=mp.end();it++)
{
if(it->from == from && !visit[it->to])
{
//printf("%d to %d\n",it->from,it->to);
visit[it->to] = 1;
num[depth] ++;
dfs(it->to);
}
if(it->from != from)
break;
}
depth--;
}
int main()
{
int n;
int ans = 0;
cin>>n;
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
edge tmp(a,b);
mp.push_back(tmp);
}
sort(mp.begin(),mp.end(),cmp);
visit[1] = 1;
dfs(1);
for(int i=2;num[i];i++)
{
ans += (num[i] - 1) * 2 + 1;
//printf("num[%d] = %d\n",i,num[i]);
}
cout<<ans<<endl;
return 0;
}
第一题,dfs记录树的深度的数量存在num数组
ans += (num[i] - 1) * 2 + 1;
查看原帖
点赞 5
相关推荐

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 不卡学历的大厂有哪些? #
4907次浏览 50人参与
# 百度秋招提前批进度 #
108297次浏览 1144人参与
# 实习如何「偷」产出? #
11782次浏览 151人参与
# 除了主业以外,你还有哪些其他收入? #
2467次浏览 55人参与
# 实习打杂,要跑路吗 #
6779次浏览 94人参与
# 风评不好的公司,你会去吗? #
39989次浏览 263人参与
# 校园里的破防时刻 #
4098次浏览 50人参与
# 职场新人体验 #
8421次浏览 92人参与
# 为什么那么多公司毁约 #
180788次浏览 1339人参与
# 蔚来求职进展汇总 #
92614次浏览 769人参与
# 第一份工作应该选高薪还是热爱? #
76426次浏览 735人参与
# 一人推荐一个值得去的通信/硬件公司 #
187878次浏览 1867人参与
# 设计人如何选offer #
127035次浏览 746人参与
# 考研可以缓解求职焦虑吗 #
52550次浏览 470人参与
# 学历贬值真的很严重吗? #
27402次浏览 186人参与
# 秋招结束之后的日子 #
77328次浏览 940人参与
# 腾讯求职进展汇总 #
951623次浏览 9568人参与
# 你觉得现在还能进互联网吗? #
16293次浏览 178人参与
# 你觉得早上几点上班合适? #
74156次浏览 308人参与
# 24届软件开发秋招薪资爆料 #
355562次浏览 1229人参与