引: \(\color{Yellow}水何澹澹,山岛竦峙。\)
Solution
这是一棵无根树, 所以据此使用点分治。
点分治适合处理大规模的树上路径信息问题。
我们先随意选择一个节点作为根节点 \(\mathit{rt}\),所有完全位于其子树中的路径可以分为两种,一种是经过当前根节点的路径,一种是不经过当前根节点的路径。对于经过当前根节点的路径,又可以分为两种,一种是以根节点为一个端点的路径,另一种是两个端点都不为根节点的路径。而后者又可以由两条属于前者链合并得到。所以,对于枚举的根节点 \(\mathit{rt}\),我们先计算在其子树中且经过该节点的路径对答案的贡献,再递归其子树对不经过该节点的路径进行求解。
-- Oi Wiki
有了这个思路, 我们可以只考虑经过当前子树的根的路径,对于新加入的一个子节点信息,我们统计出到达每个节点的距离,并使用dp来维护信息即可。
Attention
点分治的本质是优化暴力 --Pink Rabit
我们向下递归处理子树时,要找到子树的重心并将其赋为根节点,这样每递归一次,最大的子树大小不超过整棵树大小的一般,最多递归 \(O(logN)\) 层,因此保证了时间复杂度。
时间复杂度 \(O(n \ log \ n)\)
C++ 代码
#include <bits/stdc++.h>
#define for_(i,a,b) for (int i = (a); i < (b); i++)
#define rep_(i,a,b) for (int i = (a); i <= (b); i++)
#define per_(i,a,b) for (int i = (a); i >= (b); i--)
#define ll long long
using namespace std;
const int maxn = 4e5 + 10, mod = 1e9 + 7;// mod = 1949777;
const int inf = 2e9, up = 1e7;
const double EPS = 1e-3;
int n, m, sum;
int tot = 1, rt;
int nxt[maxn], head[maxn], to[maxn], c[maxn];
int q[maxn], sz[maxn], maxx[maxn], vis[maxn], dist[maxn];
void add(int u, int v, int w) {
nxt[++tot] = head[u]; to[tot] = v; c[tot] = w; head[u] = tot;
}
void Siz(int u, int fa) {
sz[u] = 1;
maxx[u] = 0;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v != fa && !vis[v]) {
Siz(v, u);
maxx[u] = max(maxx[u], sz[v]);
sz[u] += sz[v];
}
}
maxx[u] = max(maxx[u], sum - maxx[u]);
if (maxx[u] < maxx[rt]) rt = u;
}
int dd[maxn], cnt;
int p[maxn], l[maxn];
void Dist(int u, int D, int fa) {
dd[++cnt] = D;
p[u] = p[fa] + 1;
l[cnt] = p[u];
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v != fa && !vis[v]) {
Dist(v, D + c[i], u);
}
}
}
int k;
int ans = inf;
queue<int> tag;
int dp[up];
void dfs(int u) {
vis[u] = 1;
dp[0] = 0;
tag.push(0);
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) {
cnt = 0;
Dist(v, c[i], 0);
for (int j = 1; j <= cnt; j++) {
if (dd[j] <= k && dp[k - dd[j]] != -1) ans = min(ans, dp[k - dd[j]] + l[j]);
}
for (int j = 1; j <= cnt; j++) {
if (dd[j] <= k) {
if (dp[dd[j]] == -1 || dp[dd[j]] > l[j]) dp[dd[j]] = l[j], tag.push(dd[j]);
}
}
}
}
while(!tag.empty()) dp[tag.front()] = -1, tag.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) {
rt = 0; sum = sz[v]; Siz(v, 0); Siz(rt, 0);
dfs(rt);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
memset(dp, -1, sizeof(dp));
rep_(i, 1, n - 1) {
int u, v, w; cin >> u >> v >> w; u++, v++; add(u, v, w); add(v, u, w);
}
maxx[0] = inf;
sum = n;
rt = 0;
Siz(1, 0);
Siz(rt, 0);
dfs(rt);
cout << (ans != inf ? ans : -1) << endl;
return 0;
}
标签:rt,maxx,int,分治,maxn,权值,节点,dp From: https://www.cnblogs.com/Cranew/p/17247409.html