最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天简讯:权值（点分治）

来源：博客园


【资料图】

264. 权值 - AcWing题库

引： \(\color{Yellow}水何澹澹,山岛竦峙。\)

Solution

这是一棵无根树， 所以据此使用点分治。

点分治适合处理大规模的树上路径信息问题。

我们先随意选择一个节点作为根节点 \(\mathit{rt}\)，所有完全位于其子树中的路径可以分为两种，一种是经过当前根节点的路径，一种是不经过当前根节点的路径。对于经过当前根节点的路径，又可以分为两种，一种是以根节点为一个端点的路径，另一种是两个端点都不为根节点的路径。而后者又可以由两条属于前者链合并得到。所以，对于枚举的根节点 \(\mathit{rt}\)，我们先计算在其子树中且经过该节点的路径对答案的贡献，再递归其子树对不经过该节点的路径进行求解。

-- Oi Wiki

有了这个思路， 我们可以只考虑经过当前子树的根的路径，对于新加入的一个子节点信息，我们统计出到达每个节点的距离，并使用dp来维护信息即可。

Attention

点分治的本质是优化暴力--Pink Rabit

我们向下递归处理子树时，要找到子树的重心并将其赋为根节点，这样每递归一次，最大的子树大小不超过整棵树大小的一般，最多递归 \(O(logN)\) 层，因此保证了时间复杂度。

时间复杂度 \(O(n \ log \ n)\)

C++ 代码

#include #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 longusing 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 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;}

关键词：