企业官网建设流程全解析

P9725 [EC Final 2022] Chase Game 2

题目描述

庞教授和寿教授喜欢玩追逐游戏。

游戏地图由n nn个房间和n − 1 n-1n−1条双向通道组成。游戏地图是连通的。这意味着地图形成一棵树。

一开始，庞教授在房间u uu，而寿教授在房间v vv（u ≠ v u\neq vu=v）。庞教授和寿教授轮流玩游戏，寿教授先开始。在自己的回合中，玩家知道自己所在的位置和另一个玩家的位置，可以决定留在当前房间或者移动到与当前房间直接通过通道相连的另一个房间。当庞教授和寿教授在同一个房间时，寿教授被庞教授抓住。

庞教授和寿教授足够聪明。庞教授希望在有限的回合内抓住寿教授。寿教授不希望在任何有限的回合内被庞教授抓住。

寿教授厌倦了每次都被抓住，找到了费教授寻求帮助。寿教授请求费教授添加一些通道，使得无论初始房间对( u , v ) (u,v)(u,v)如何，庞教授都无法在有限的回合内抓住他。费教授很懒，所以他希望尽可能少地添加通道。如果无论如何添加通道，总是存在一对房间( u , v ) (u,v)(u,v)，使得庞教授能够抓住寿教授，输出− 1 -1−1。

输入格式

第一行包含一个整数T TT(1 ≤ T ≤ 10 4 1\le T\le 10^41≤T≤104)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数n nn(2 ≤ n ≤ 10 5 2\le n\le 10^52≤n≤105)，表示房间的数量。

接下来的n − 1 n-1n−1行，每行包含两个整数u uu和v vv(1 ≤ u , v ≤ n 1\le u, v\le n1≤u,v≤n)，表示连接房间u uu和房间v vv的通道。

保证所有测试用例中n nn的总和不超过2 × 10 5 2\times 10^52×105，并且房间和通道始终构成一棵树。

对于每个测试用例，输出一个数字表示添加的通道的最小数量，或者只输出− 1 -1−1。

输出格式

输出一行整数，表示答案。

翻译来自于：ChatGPT

输入输出样例 #1

输入 #1

4 2 1 2 4 1 2 2 3 3 4 4 1 2 2 3 2 4 5 1 2 2 3 3 4 3 5

输出 #1

-1 1 -1 2

C++实现

#include<cstdio>#include<cstring>constintN=1e5+5;intT,n,du[N],u[N],v[N],tj[N],sum,ans;boolbb;intmain(){scanf("%d",&T);while(T--){memset(du,0,sizeof(du));memset(tj,0,sizeof(tj));sum=0;bb=1;//多测不清空，挂分两行泪。scanf("%d",&n);for(inti=1;i<n;i++)scanf("%d%d",&u[i],&v[i]),du[u[i]]++,du[v[i]]++;//du[x] 表示 x 的度数if(n<=3){puts("-1");continue;}for(inti=1;i<n;i++){if(du[u[i]]==1)tj[v[i]]++,sum++;if(du[v[i]]==1)tj[u[i]]++,sum++;//统计每一个父亲有的叶子节点数量}ans=((sum+1)>>1);//考试时因为没向上取整，吃了一发罚时 (record:127986514)。for(inti=1;i<=n;i++)if(tj[i]==sum){puts("-1");bb=0;continue;}//所有叶子节点的父亲都是同一个节点，无解。elseif(tj[i]>ans)ans=tj[i];//有剩余的if(bb)printf("%d\n",ans);}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容