本文主要是介绍树上直径---巨木之森,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
定理---树上任意一点的最远点一定是树的直径的端点。
可以发现,要想遍历完整颗树,再回到原来的位置,那么就要把每条边都走两遍,但是现在不需要回到原来的位置,所以只要找到离根节点最远的点,用总权值的两倍减去 这条最远边的长度就好了。
于是,我们可以先以某点dfs,求出这点的最远距离----一定是树直径的是某个端点p。
再以该点p出发,dfs找出另一个端点 q;
最后,再dfs q点求出所有点到q点的距离,之后计算,排序求解即可。
#include<bits/stdc++.h>
//树的深搜
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, M = 2 * N;ll n, m;
ll d[N];
bool st[N];
int h[N],e[M],ne[M],idx;
ll edge[N];
ll q[N];
ll dis1[N];
ll dis2[N];
void add (int a,int b,ll c)
{e[idx]=b;ne[idx]=h[a];edge[idx] = c;h[a]=idx++;}void dfs(ll dis[],int u,int fa)
{for(int i = h[u] ; i != - 1 ; i = ne[i] ){int j = e[i];if(j == fa) continue;dis[j] = max(dis[j],dis[u] +edge[i] );dfs(dis,j,u);}
}int main()
{memset(h,-1,sizeof h);cin >> n >> m;ll x ,y,z;ll all = 0;for(int i = 1 ; i < n ;i++){cin >> x >> y >> z;all += z;add(x,y,z);add(y,x,z);}int maxv = 1;dfs(dis1,maxv,0);for(int i = 2 ;i <= n ;i++) if(dis1[i] > dis1[maxv]) maxv = i;memset(dis1,0,sizeof dis1);dfs(dis1,maxv,0);int se = 1;for(int i = 2 ;i <= n ;i++) if(dis1[i] > dis1[se]) se = i;dfs(dis2,se,0);//z = 2;// cout << all << endl;for(int i = 1 ;i <= n ;i++){q[i] = 2ll * all - max(dis1[i],dis2[i]);}sort(q + 1, q + 1 + n);ll ans = 0;int i = 1;for(;i<=n;i++){if(q[i]>m)break;else m-=q[i];}cout << i - 1 << endl;// cout << i - 1 <<endl;
}
这篇关于树上直径---巨木之森的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!