巨木之森（树的路径，贪心）

巨木之森（树的路径，贪心）

巨木之森

• 巨木之森（树的路径，贪心）
• • 题意
  • 数据范围
  • 思路
  • 代码

巨木之森（树的路径，贪心）

巨木之森

题意

给定一棵 n n n个结点的树， m m m块钱。定义花费为从一个点出发遍历整棵树所经过的路径和。求最多能选择多少个不同的起点使得花费总和 ≤ m leq m ≤m。

数据范围

n ≤ 1 0 5 , m ≤ 1 0 18 , w i ≤ 1 0 8 n leq 10^5, m leq 10^{18},w_i leq 10^8 n≤105,m≤1018,wi​≤108

思路

这道题问的是路径和，所以要从每条边计算几次入手。可以将树画成一条链，链的两侧有若干子树的形状，这样问题会变得更加直观。
我们很容易发现，在一个花费中，一条链被计算 1 1 1次，其余边权被计算 2 2 2次。假设这条链的长度为 l e n len len，整棵树所有边权和为 t o t a l total total，则花费即为 l e n + 2 ∗ ( t o t a l − l e n ) = 2 ∗ t o t a l − l e n . len+2*(total - len) = 2 * total - len. len+2∗(total−len)=2∗total−len.
我们根据式子，可以发现花费只与链的长度有关。因此，为了使每次花费最少，我们可以选取以起点为一个端点的最长链。求出以每个点为起点的最长链，在从大到小遍历一遍，统计出答案，问题就解决了。
代码的书写就是个套模板的过程。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;typedef long long ll;
const int N = 100010, M = 2 * N;
const ll INF = 2e18;int n;
ll m;
int h[N], e[M], ne[M], idx;
ll w[M];
ll d1[N], d2[N], p1[N], up[N], len[N];
bool is_leaf[N];void add(int a,int b,ll c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}ll dfs_d(int u, int father)
{d1[u] = d2[u] = -INF;for(int i=h[u];~i;i=ne[i]){int j = e[i];if(j==father) continue;ll d = dfs_d(j, u) + w[i];if(d>=d1[u]){d2[u] = d1[u], d1[u] = d;p1[u] = j;}else if(d>d2[u]) d2[u] = d;}if(d1[u]==-INF){d1[u] = d2[u] = 0;is_leaf[u] = true;}return d1[u];
}void dfs_u(int u, int father)
{for(int i=h[u];~i;i=ne[i]){int j = e[i];if(j==father) continue;if(p1[u]==j) up[j] = max(up[u], d2[u]) + w[i];else up[j] = max(up[u], d1[u]) + w[i];dfs_u(j, u);}
}int main()
{scanf("%d%lld",&n,&m);memset(h,-1,sizeof(h));ll tot = 0;for(int i=1;i<n;i++){int a,b;ll c;scanf("%d%d%lld",&a,&b,&c);add(a,b,c), add(b,a,c);tot += c;}tot *= 2;dfs_d(1, -1);dfs_u(1, -1);len[1] = d1[1];for(int i=2;i<=n;i++){if (is_leaf[i]) len[i] = up[i];else len[i] = max(d1[i], up[i]);}sort(len+1,len+1+n);int ans = 0;for(int i=n;i>=1;i--){if(m<=0) break;else{m -= (tot - len[i]);if(m>=0) ans ++;}}printf("%dn",ans);return 0;
}