求树的根时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多描述给定一棵包含n nn个节点的有根树节点编号为1 ∼ n 1 \sim n1∼n。输入以n − 1 n - 1n−1条有向边( a i , b i ) (a_i, b_i)(ai​,bi​)表示存在一条从a i a_iai​指向b i b_ibi​的边且整棵树构成一棵树。请输出树的根节点编号唯一入度为0 00所有叶子节点编号出度为0 00按升序排列。输入描述第一行输入整数n ( 1 ≤ n ≤ 10 5 ) n\ (1 \le n \le 10^5)n(1≤n≤105)。接下来n − 1 n - 1n−1行每行输入两个整数a i , b i ( 1 ≤ a i , b i ≤ n ) a_i, b_i\ (1 \le a_i, b_i \le n)ai​,bi​(1≤ai​,bi​≤n)表示一条有向边a i → b i a_i \to b_iai​→bi​。输出描述第一行输出根节点编号。第二行输出所有叶子节点编号升序空格分隔。示例 1输入3 1 2 1 3输出1 2 3数据范围与提示1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤1051 ≤ a i , b i ≤ n 1 \le a_i, b_i \le n1≤ai​,bi​≤n输入保证构成一棵有根树因此入度为0 00的节点恰有一个。核心做法用两个数组分别统计每个节点的入度与出度入度为0 00的节点即为根出度为0 00的节点即为叶子用vector收集后一次性输出即可从小到大枚举节点编号天然有序无需额外排序。边界情况n 1 n 1n1时没有输入边此时根与叶子都是节点1 11需要特判。时间复杂度O ( n ) O(n)O(n)。解题思路本题是有根树基本性质统计的入门题。给定一棵有n nn个节点的有根树边以有向边( a i , b i ) (a_i, b_i)(ai​,bi​)的形式给出表示a i a_iai​指向b i b_ibi​要求找出根节点入度为0 00的唯一节点和所有叶子节点出度为0 00的节点并按升序输出叶子编号。只需统计每个节点的入度和出度即可在线性时间内完成。1. 问题等价转化有根树中根节点没有父节点因此其入度为0 00其余节点均有且仅有一个父节点入度为1 11。叶子节点没有子节点因此其出度为0 00非叶子节点至少有一个子节点出度大于0 00。题目保证输入构成一棵合法的有根树因此入度为0 00的节点恰好有一个即为根节点。叶子节点可能有多个需要收集所有出度为0 00的节点并按编号升序输出。2. 算法实现输入处理读入n nn。若n 1 n 1n1则只有一个节点它既是根也是叶子直接输出1和1。创建两个数组inDeg和outDeg大小均为n 1 n1n1初始化为0 00分别统计每个节点的入度和出度。循环读入n − 1 n-1n−1条有向边( x , y ) (x, y)(x,y)inDeg[y]y yy的入度加一outDeg[x]x xx的出度加一。寻找根节点遍历节点编号1 ∼ n 1 \sim n1∼n找到第一个inDeg[i] 0的节点输出其编号即为根。收集叶子节点创建vectorll leaves。再次遍历节点编号1 ∼ n 1 \sim n1∼n若outDeg[i] 0则将i ii加入leaves。由于遍历顺序是从小到大leaves中元素天然升序无需额外排序代码中sort是冗余但无害的。输出叶子按顺序输出leaves中的元素空格分隔最后换行。3. 复杂度分析时间复杂度读入边并统计入度、出度需要O ( n ) O(n)O(n)遍历节点找根和叶子也是O ( n ) O(n)O(n)。总时间复杂度O ( n ) O(n)O(n)。n ≤ 10 5 n \le 10^5n≤105完全可行。空间复杂度需要两个长度为n 1 n1n1的数组和存储叶子的向量空间复杂度O ( n ) O(n)O(n)。总结利用有根树中根节点入度为0 00、叶子节点出度为0 00的性质只需一次遍历统计度数即可快速确定根和所有叶子。注意n 1 n1n1的边界情况需特判。该方法简单高效是树结构基础操作的典型应用。代码简要说明solve()函数处理单组数据读入n nn特判n 1 n1n1。数组a统计入度b统计出度。循环n − 1 n-1n−1次读入边更新a[y]和b[x]。遍历1 ∼ n 1 \sim n1∼n找到a[i] 0输出根。遍历1 ∼ n 1 \sim n1∼n将b[i] 0的节点加入c排序后输出。主函数调用solve()使用快速 I/O。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n;cinn;if(n1){cout1\n1\n;return;}vectorlla(n1,0);vectorllb(n1,0);for(ll i1;in;i){ll x,y;cinxy;a[y];b[x];}for(ll i1;in;i){if(a[i]0){couti\n;break;}}vectorllc;for(ll i1;in;i)if(b[i]0)c.push_back(i);sort(c.begin(),c.end());for(ll i0;i(ll)c.size()-1;i)coutc[i] ;cout\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}