树上直径---巨木之森

2024-01-15 07:40
文章标签 树上 直径 巨木之森

本文主要是介绍树上直径---巨木之森,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

定理---树上任意一点的最远点一定是树的直径的端点。

可以发现,要想遍历完整颗树,再回到原来的位置,那么就要把每条边都走两遍,但是现在不需要回到原来的位置,所以只要找到离根节点最远的点,用总权值的两倍减去 这条最远边的长度就好了。

于是,我们可以先以某点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;
}

这篇关于树上直径---巨木之森的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_52048593/article/details/123139332
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/608142

相关文章

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

【codechef】 Prime Distance On Tree【求树上路经长度为i的路径条数】【点分治+FFT】

传送门:【codechef】 Prime Distance On Tree 点分治+FFT水题……竟然n*n爆int没发现…… 而且NTT TLE,FFT跑的超级快…… my  code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) m

poj 1849 Two(树形dp求直径)

树的直径:一棵树中两个点间的最长距离。 Description The city consists of intersections and streets that connect them.  Heavy snow covered the city so the mayor Milan gave to the winter-service a list of streets that ha

POJ 1985 Cow Marathon(树的直径)

题目链接 题意:给出一棵树,求出这个树的直径 解答:任选一点进行dfs,会找到一个最远点s,在以这个最远点s进行dfs,会找到一个最远点是t,那么s-t就是树的直径。 //#include<bits/stdc++.h>#include<cstdio>#include<algorithm>#include<vector>#include<cstring>using namespace

F. LIS on Tree 树上根路径LIS

1 关于lower_bound // 12345 查4 应该放在4 。而不是5的位置。。所以不是uppper。 //如果1235 查4 。可以优化5 。 2 关于 ans[u] = max(j, ans[p]); 维护一个max 一定从(premax,cur)中选出来的。 3 关于 memset(st, 0x3f, sizeof st); 这个和st + 1, st + n + 1 。。我们二分选

SDUT OJ 3045 迷之图论 (树的直径)

题目地址:SDUT OJ 3045 这题比赛的时候想的差不多。。但是总是觉得不对。。写了一次就没再写,然后删了。。当时没想到的是第二次求出来的就是最长链。。当时想到的两次bfs找最大值(这一种方法其实结果也对。。TAT。。),还有找到点后在回溯减去重点等等。。但总觉得好像都不太对。。。赛后才知道这题原来是树的直径。。。。。牡丹江区域现场赛的时候遇到过,不过赛后也没看。。。 找树的直径的方法其实

HDU 5016 Mart Master II (树上点分治)

题目地址:HDU 5016 先两遍DFS预处理出每个点距最近的基站的距离与基站的编号。 然后找重心,求出每个点距重心的距离,然后根据dis[x]+dis[y] < d[y],用二分找出当前子树中不会被占领的数量,总点数减去即是被占领的数量。这样就可以求出每个点最多占领的点的数量。然后找最大值即可。 代码如下: #include <iostream>#include <string.h>

HDU 4871 Shortest-path tree (最短路+树上点分治)

题目地址:HDU 4871 先用最短路求出根节点到其它各点的最短距离,然后利用最短距离DFS一下构造出最短路树,然后剩下的就是在构造出来的这棵树上做树分治,很简单的树分治。 代码如下: #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include

SPOJ 1825 FTOUR2 - Free tour II (树上点分治)

题目地址:SPOJ 1825 树分治的题果然除了模板题就是金牌题啊。。。这题是一道论文题,想了好长时间。。。。终于过了,,,,注意一个坑点,如果权值全部为负的话,是可以不选任意一条边的,这样权值为0。。。也就是说初始值要设为0。。。 具体看漆子超的论文《分治算法在树的路径问题中的应用》。。 代码如下: #include <iostream>#include <string.h>#inc

BZOJ 2152 聪聪可可 (树上点分治)

题目地址:BZOJ 2152 找有多少对权值和为3的倍数的点。最简单的点分治。 代码如下: #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#incl