Tree Queries (Hard Version)
算法本质
思维
题目大意
给定一颗树（边权默认1），其存在一个开局固定但是玩家不知道的点称之为终点。
在这个游戏中，玩家可有进行询问：
- 每次询问玩家给出某点
x，系统会回答终点与x点的距离
游戏目标是完成某次询问后说出终点位置。
玩家总是希望用最少的次数搞定游戏，在游戏开始前，Alice问玩家至多需要几次询问。
输出至多询问次数即可。
思路推演
首先我们需要搞定游戏规则。
先从简单的开始模拟——一条链。
显然如果我们询问链的某个端点，只需要一次就可以判断终点位置了，这也给了一个trick——询问总是在叶节点。
然后可以从爪字型继续模拟，发现仅需要2次询问即可。
而且我们加长某条链，询问次数不变，说明变化是在度>=3的点上发生的。
但是当扩展到更复杂的情况时，会遇到一些问题。
我们希望其存在某些规律，可以用树dfs搞定，但是如果以节点为单位看的话，显然是错误的。
于是我们假设，使用dfs遍历时，根节点默认选择。
在根节点默认选择这个条件下模拟，规律相对明显。
首先可知，如果选择所有叶节点，一定是可行的，我们可以给叶节点染上白色。
若白点和旁边的点可以形成链结构，则白色扩张——在思维上可以认为没有链的中间点。
现在对于任意一个非白色的点来说，如果其有n的度，其中n-1条边都是被询问激活的，另一条边指向的点是白点，则可以视作另一条变也被激活。
这里规律细节比较多，仔细思考一下
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
vector<vector<int>> g(n+5);
vector<int> vis(n+5);
m = n-1;
while (m--)
{
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
if (n==1)
{
cout<<0<<endl;
return;
}
queue<int> q;
for (int i=1; i<=n; i++)
if (g[i].size()==1)
q.push(i), vis[i]=1; // vis[x]=1表示白点
while (q.size()) // 白点扩张
{
int u=q.front();
q.pop();
for (int v:g[u])
{
if (g[v].size()==2 && vis[v]==0)
{
q.push(v);
vis[v]=1;
}
}
}
int ans=0;
for (int i=1; i<=n; i++)
{
if (vis[i]) continue; // 找到非白点
int cnt=0; // 非白点之间可以视作默认激活
for (int v:g[i])
cnt += vis[v];
ans += max(0ll, cnt-1);
}
ans = max(1ll, ans); // 因为0的情况已经被特判出去了
cout<<ans<<endl;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)