# 2022 ICPC 济南站 L 题题解()-其他

## 2022 ICPC 济南站 L 题题解()

### 代码

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
using ll = long long;
const int N = 2e5 + 5, Q = 1e6 + 5;
int n, q, vis[N], siz[N], mxsiz[N];
vector<pair<int, int>> e[N];
void GetRoot(int u, int fa, int tot, int& rt) {
siz[u] = 1, mxsiz[u] = 0;
for (auto [v, w] : e[u]) if (v != fa && !vis[v]) {
GetRoot(v, u, tot, rt);
siz[u] += siz[v], mxsiz[u] = max(mxsiz[u], siz[v]);
}
mxsiz[u] = max(mxsiz[u], tot - siz[u]);
if (!rt || mxsiz[u] < mxsiz[rt]) rt = u;
}
vector<pair<int, ll>> dis[N], dep;
void GetDep(int u, int fa, ll curd) {
dep.emplace_back(u, curd);
for (auto [v, w] : e[u]) if (v != fa && !vis[v]) {
GetDep(v, u, curd + w);
}
}
void Solve(int u) {
int rt = 0; GetRoot(u, 0, siz[u], rt), u = rt, vis[u] = 1;
dep.clear(), GetDep(u, 0, 0);
sort(dep.begin(), dep.end());
static int stk[N];
for (int i = 0, tp = 0; i<int(dep.size()); ++i) {
auto [v, w] = dep[i];
while (tp && dep[stk[tp]].second > w) --tp;
if (tp) dis[v].emplace_back(dep[stk[tp]].first, w + dep[stk[tp]].second);
stk[++tp] = i;
}
for (int i = int(dep.size()) - 1, tp = 0; ~i; --i) {
auto [v, w] = dep[i];
while (tp && dep[stk[tp]].second > w) --tp;
if (tp) dis[dep[stk[tp]].first].emplace_back(v, w + dep[stk[tp]].second);
stk[++tp] = i;
}
for (auto [v, w] : e[u]) if (!vis[v]) Solve(v);
}
vector<pair<int, int>> qry[N];
struct BIT {
ll t[N];
void Upd(int p, ll x) { for (; p <= n; p += p & -p) t[p] = min(t[p], x); }
ll Query(int p) { ll res = 1LL << 60; for (; p; p &= p - 1) res = min(res, t[p]); return res; }
}bit;
ll ans[Q];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n;
For(i, 1, n - 1) {
int u, v, w; cin >> u >> v >> w;
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
siz[1] = n, Solve(1);
cin >> q;
For(i, 1, q) {
int l, r; cin >> l >> r;
qry[r].emplace_back(l, i);
}
memset(bit.t, 0x3f, sizeof(bit.t));
For(r, 1, n) {
for (auto [l, w] : dis[r]) bit.Upd(n - l + 1, w);
for (auto [l, id] : qry[r]) {
if (l == r) ans[id] = -1;
else ans[id] = bit.Query(n - l + 1);
}
}
For(i, 1, q) cout << ans[i] << '\n';
return 0;
}

————————

### 代码

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
using ll = long long;
const int N = 2e5 + 5, Q = 1e6 + 5;
int n, q, vis[N], siz[N], mxsiz[N];
vector<pair<int, int>> e[N];
void GetRoot(int u, int fa, int tot, int& rt) {
siz[u] = 1, mxsiz[u] = 0;
for (auto [v, w] : e[u]) if (v != fa && !vis[v]) {
GetRoot(v, u, tot, rt);
siz[u] += siz[v], mxsiz[u] = max(mxsiz[u], siz[v]);
}
mxsiz[u] = max(mxsiz[u], tot - siz[u]);
if (!rt || mxsiz[u] < mxsiz[rt]) rt = u;
}
vector<pair<int, ll>> dis[N], dep;
void GetDep(int u, int fa, ll curd) {
dep.emplace_back(u, curd);
for (auto [v, w] : e[u]) if (v != fa && !vis[v]) {
GetDep(v, u, curd + w);
}
}
void Solve(int u) {
int rt = 0; GetRoot(u, 0, siz[u], rt), u = rt, vis[u] = 1;
dep.clear(), GetDep(u, 0, 0);
sort(dep.begin(), dep.end());
static int stk[N];
for (int i = 0, tp = 0; i<int(dep.size()); ++i) {
auto [v, w] = dep[i];
while (tp && dep[stk[tp]].second > w) --tp;
if (tp) dis[v].emplace_back(dep[stk[tp]].first, w + dep[stk[tp]].second);
stk[++tp] = i;
}
for (int i = int(dep.size()) - 1, tp = 0; ~i; --i) {
auto [v, w] = dep[i];
while (tp && dep[stk[tp]].second > w) --tp;
if (tp) dis[dep[stk[tp]].first].emplace_back(v, w + dep[stk[tp]].second);
stk[++tp] = i;
}
for (auto [v, w] : e[u]) if (!vis[v]) Solve(v);
}
vector<pair<int, int>> qry[N];
struct BIT {
ll t[N];
void Upd(int p, ll x) { for (; p <= n; p += p & -p) t[p] = min(t[p], x); }
ll Query(int p) { ll res = 1LL << 60; for (; p; p &= p - 1) res = min(res, t[p]); return res; }
}bit;
ll ans[Q];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n;
For(i, 1, n - 1) {
int u, v, w; cin >> u >> v >> w;
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
siz[1] = n, Solve(1);
cin >> q;
For(i, 1, q) {
int l, r; cin >> l >> r;
qry[r].emplace_back(l, i);
}
memset(bit.t, 0x3f, sizeof(bit.t));
For(r, 1, n) {
for (auto [l, w] : dis[r]) bit.Upd(n - l + 1, w);
for (auto [l, id] : qry[r]) {
if (l == r) ans[id] = -1;
else ans[id] = bit.Query(n - l + 1);
}
}
For(i, 1, q) cout << ans[i] << '\n';
return 0;
}