军营选择_腾讯音乐娱乐集团笔试题

牛牛是一名新晋营长，需要选择军营建造地点，已知一共有 $\mathit n$ 个候选地，编号为 $\text 1,\ \text 2,\ ...,\ \mathit n$ ，有 $\mathit n\ -\ \text 1$ 条道路，使得这 $\mathit n$ 个候选地之间两两可以到达。

军营选择规则如下：

对于其中一个候选地 $\mathit i$ 而言，如果将该地以及其直接相连的道路全都删除，就可以得到若干个连通块，用 $\mathit w_\mathit i$ 记录下其中的最大连通块中的候选地数量。

对于所有的满足 $\mathit w_\mathit k\ =\ \mathit {min}\{\mathit w_\text 1,\ \mathit w_\text 2,\ ...,\ \mathit w_\mathit n\}$ 的候选地 $\mathit k$ 而言，都是最佳军营建造地。

由于最佳地点可能不止一个，所以牛牛想要通过一些操作将该地点唯一化：

首先，牛牛会封闭一条已经存在的道路，接着，构建一条新道路，在这两个操作之后，这 $\mathit n\ -\ \text 1$ 条道路依然可以使 $\mathit n$ 个地点两两相通，同时，最佳地点只有一个。

但是，牛牛只擅长指挥军队，并不精通此法，所以，请你给出任意一种可以达成要求的合法方案。

本题为多组测试数据，第一行输入一个正整数 $\mathit T(\text 1\ \leq\ \mathit T\ \leq\ \text {10} ^ \text 5)$ ，代表测试数据组数。

对于每组测试数据，第一行输入一个正整数 $\mathit n(\text 3\ \leq\ \mathit n\ \leq\ \text {10} ^ \text 5)$ ，代表军营候选地的数量。
接下去 $\mathit n\ -\ \text 1$ 行，每行两个正整数 $\mathit u,\ \mathit v(\text 1\ \leq\ \mathit u,\ \mathit v\ \leq\ \mathit n;\ \mathit u\ \ne\ \mathit v)$ ，代表候选地 $\mathit u,\ \mathit v$ 之间存在一条道路 (无向边)。

数据保证，每组测试数据给出的道路一定可以使 $\mathit n$ 个候选地两两相通，同时，所有测试数据的 $\mathit n$ 之和不会超过 $\text {10} ^ \text 6$ .

对于每组测试数据，输出两行，第一行输出两个正整数 $\mathit u_\text 1,\ \mathit v_\text 1$ ，代表封闭原道路 $\mathit u_\text 1,\ \mathit v_\text 1$ ，这条道路必须存在。
第二行输出两个正整数 $\mathit u_\text 2,\ \mathit v_\text 2$ ，代表增加一条道路 $\mathit u_\text 2,\ \mathit v_\text 2$ ，这条道路必须在原道路中不存在或者已经被封闭。
由于是无向边，所以输出 $\mathit u,\ \mathit v$ 等价于 $\mathit v,\ \mathit u$ .

如果存在多种解，任意输出一种即可，只需要保证满足题意。

第一组测试数据中，最佳选择本就只有一个，所以任选一条道路，封闭后再建造即可。
第二组测试数据中，最佳选择为候选地 $\text 1,\ \text 3$ ，而在封闭 $\text {3 4}$ 之间的道路，再添加 $\text {4 1}$ 之间的道路之后，最佳选择就只有候选地 $\text 1$ .

#include <bits/stdc++.h> typedef long long ll; using namespace std; int t,n,w[100005],minnode=1e9; vector<int>e[100005]; int dfs(int root,int f) { /**< dfs返回值是以root为根子树的节点数量*/ int sum=1,maxv=0; for(int i=0;i<e[root].size();i++) { int y=e[root][i]; if(y==f) continue; int temp=dfs(y,root); sum+=temp; maxv=max(maxv,temp);/**< 求root子树节点数最大值 */ } w[root]=max(n-sum,maxv);/**< 记录下删除root后的最大连通块wi */ minnode=min(minnode,w[root]);/**< 求最小wi的值 */ return sum; } int main() { ios::sync_with_stdio(0),cin.tie(0); // freopen(".in","r",stdin); // freopen(".out","w",stdout); int i,j,x,y; cin>>t; while(t--) { minnode=1e9; cin>>n; for(i=1;i<=n;i++) e[i].clear(),w[i]=0; for(i=1;i<n;i++) { cin>>x>>y; e[x].push_back(y),e[y].push_back(x); } dfs(1,0); int s1=0,s2=0; for(i=1;i<=n;i++) if(w[i]==minnode) {/**< 找到2个最小值的节点，感觉树应该是对称的 */ if(s1==0) s1=i; else s2=i; } if(s2==0)/**< 只有一个节点 */ cout<<1<<' '<<e[1][0]<<endl<<1<<' '<<e[1][0]<<endl; else { /**< 把第二个节点中一颗子树转移给第一个节点 */ for(i=0;i<e[s2].size();i++) if(e[s2][i]!=s1) break; cout<<s2<<' '<<e[s2][i]<<endl<<s1<<' '<<e[s2][i]<<endl; } } return 0; }

军营选择

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题