巨木之森
巨木之森（树的路径，贪心）题意数据范围思路代码
巨木之森（树的路径，贪心）
巨木之森
题意
给定一棵
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("%d\n",ans
);
return 0;
}
