//跑不过,不知道为啥,感觉逻辑都很正确了 //题意:给出一棵带边权的树,询问一条权值为k的路径经过点的最小值是多少 //思路:因为涉及到最小值问题,所以树性dp好像不行(其实暂时不清楚,因为dp没怎么碰过) // 然后这种路径可合并问题很明显是可以用dsu on tree做的 因为没有树上修改的步骤 // /*# include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10; struct edge { int to, w; edge(int a = 0, int b = 0) { to = a, w = b; } }; int n, k, ans = 1e9; vector<edge> mp[N]; int dep[N], dep1[N], f[N], sz[N], son[N], id[N], nid[N], cnt; map<int, int> depp;//用于记录已经出现的路径长度,因为我们要求的是最小深度,所以我们哈希值为 最小深度 void dfs(int x, int fa) { sz[x] = 1; f[x] = fa; id[x] = ++cnt; nid[cnt] = x; for (auto y : mp[x]) { if (y.to == fa) continue; dep[y.to] += 1; dep1[y.to] += y.w; dfs(y.to, x); sz[x] += sz[y.to]; if (sz[son[x]] < sz[y.to]) son[x] = y.to; } } void add(int x, int k) { int dp = dep1[x]; if (k == 1) { if (depp[dp] == 0||depp.find(dp)==depp.end()) depp[dp] = dep[x]; else depp[dp] = min(depp[dp], dep[x]); } else { depp[dp] = 0; } } void dfs1(int x, bool keep) { for (auto y : mp[x]) { if (y.to == son[x] || y.to == f[x]) continue; dfs1(x, 0); } if (son[x]) dfs1(son[x], 1); //用dfs序代替遍历来赋值,优化常数 //add(x, 1); for (auto y : mp[x]) { if (y.to == son[x] || y.to == f[x]) continue; for (int i = 0; i < sz[y.to]; i++) { int nxt = nid[id[y.to] + i]; int dpt = k - dep1[nxt] + 2 * dep1[x]; if (depp[dpt]) ans = min(ans, dep[nxt] + depp[dpt] - 2 * dep[x]); } //一个子树做完,再加入这个子树,保证不重复计算贡献 for (int i = 0; i < sz[y.to]; i++) add(nid[id[y.to] + i], 1); } if (!keep) for (int i = 0; i < sz[x]; i++) add(nid[id[x] + i], -1); } signed main(){ cin >> n >> k; memset(son, sizeof(son), 0); for (int i = 1; i <= n - 1; i++) { int a, b, c; cin >> a >> b >> c; a++; b++; mp[a].push_back({ b,c }); mp[b].push_back({ a,c }); } dfs(1, 0); dfs1(1, 0); if (ans == 1e9) cout << -1; else cout << ans; return 0; } */ #include<bits/stdc++.h> using namespace std; int n, k; vector <int>to[200005]; vector <int>len[200005]; long long deep[200005]; int diep[200005]; int siz[200005]; int son[200005]; int nid[200005]; int id[200005]; int cnt; map< long long, int >dep; int ans = 1e9; void dfs1(int now, int last) { siz[now] = 1; id[now] = ++cnt; nid[cnt] = now; int mx = 0; for (int i = 0; i < to[now].size(); i++) { int next = to[now][i]; if (next == last)continue; deep[next] = deep[now] + len[now][i]; diep[next] = diep[now] + 1; dfs1(next, now); siz[now] += siz[next]; if (siz[next] > mx) { mx = siz[next]; son[now] = next; } } } void updata(int x, int k) { int dx = deep[x]; if (k == -1) { dep[dx] = 0; } else { int tmp = dep[dx]; if (tmp == 0)tmp = 1e9; dep[dx] = min(tmp, diep[x]); } } void dfs2(int now, int last, bool keep) { for (auto next : to[now]) { if (next == son[now] or next == last)continue; dfs2(next, now, 0); } if (son[now])dfs2(son[now], now, 1); for (auto next : to[now]) { if (next == son[now] or next == last)continue; for (int i = 0; i < siz[next]; i++) { int nxt = nid[id[next] + i]; int req = k + 2 * deep[now] - deep[nxt]; if (dep[req]) { ans = min(ans, dep[req] + diep[nxt] - 2 * diep[now]); } } for (int i = 0; i < siz[next]; i++) { updata(nid[id[next] + i], 1); } } updata(now, 1); if (dep[deep[now] + k])ans = min(ans, dep[deep[now] + k] - diep[now]); if (keep == 0) { for (int i = 0; i < siz[now]; i++) { updata(nid[id[now] + i], -1); } } } int main() { cin >> n >> k; for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); to[u].push_back(v); to[v].push_back(u); len[u].push_back(w); len[v].push_back(w); } diep[0] = 1; dfs1(0, 0); dfs2(0, 0, 0); if (ans == 1e9)ans = -1; cout << ans; return 0; }
标签:son,int,dsu,tree,++,next,dep,Race,now From: https://www.cnblogs.com/Aacaod/p/17030253.html