题目链接
题意 : 给你一棵树,每个点有一个零食 ,某个人从1号根节点出发,每次尽量走最近的点,最后走完回到1号点,问最小的k。
思路:本来想的是二分+check 发现不可做啊,然后看了别人的题解,原来是有规律的,这道题确实和ccpc秦皇岛的蛮像,也是用的树形dp和贪心的结合,假设我们以u为根(u不是根节点的情况),那么对于每个儿子v所要满足
k
>
=
f
[
v
]
+
2
k>=f[v]+2
k>=f[v]+2
其中k是能走的最大的范围 f[v]是子节点最浅的位置,由于这个题的特殊性,每次遍历完子树,必然会停在某个叶子节点上,然后再从叶子节点转向另外一个子树,那么走的最优的方案必然是遍历完子树的最后的点停留在离u最近的叶子节点上,那么上来就会方便。然后还有个问题,为什么根节点要特判呢,因为最后回到根节点就行了,就不需要多走1步了,那么我们肯定选择走上来最困难的根的节点,也就是
f
v
fv
fv最大的,因为如果
f
v
fv
fv不加1就说明它要加2了,那肯定没有+1优秀。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=200010,M=2*N;
int dp[N],h[N],e[M],ne[M],idx,d[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int res=0;
void dfs(int u,int fa)
{
if(d[u]==1 && u!=1)
{
dp[u]=0;
return ;
}
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs(j,u);
dp[u]=min(dp[u],dp[j]+1);
}
}
vector<int>v;
void dfs2(int u,int fa)
{
int maxv=0;
//if(u==1)
if(d[u]==1 && u!=1)
return ;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
if(u==1)
{
v.push_back(dp[j]);
}
maxv=max(maxv,dp[j]);
dfs2(j,u);
}
if(u==1)
{
// cout<<v.size()<<endl;
res=max(res,maxv+1);
sort(v.begin(),v.end());
for(int i=0;i<(int)v.size()-1;i++)
res=max(res,v[i]+2);
}
else
res=max(res,maxv+2);
}
int main()
{
ios::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
v.clear();
res=0;
int n;
cin>>n;
for(int i=1;i<=n;i++)
h[i]=-1;
idx=0;
for(int i=1;i<=n;i++)
d[i]=0,dp[i]=0x3f3f3f3f;
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
d[a]++,d[b]++;
}
dfs(1,-1);
dfs2(1,-1);
cout<<res<<endl;
}
return 0;
}
/*
3
3
1 2
1 3
4
1 2
2 3
3 4
8
1 2
2 3
3 4
1 5
5 6
6 7
5 8
*/