Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
51515 | AK2022071336 | 树上博弈 | C++ | 运行超时 | 0 | 1000 MS | 12732 KB | 2040 | 2022-07-13 11:49:43 |
#include <bits/stdc++.h> using namespace std; const int N = 3e5 + 10; #define int long long int n, h[N], cnt, big, sml, U, V, w, m, R, smlr; struct ab { int v, nxt, w; }mp[N]; struct tree { int tag, lev; }tr[N]; void add(int x, int y, int z) { mp[++cnt].v = y; mp[cnt].nxt = h[x]; mp[cnt].w = z; h[x] = cnt; } void build(int node, int fa, int c) { tr[node].tag = node; tr[node].lev = c; for(int i = h[node]; i; i = mp[i].nxt) { int v = mp[i].v; if(v == fa) continue; build(v, node, c + 1); } } void solve(int l, int r) { if(tr[l].lev != tr[r].lev) { if(tr[l].lev > tr[r].lev) swap(l, r); while(tr[l].lev != tr[r].lev) { for(int i = h[r]; i; i = mp[i].nxt) { int v = mp[i].v; if(tr[v].lev < tr[r].lev) { big = max(big, mp[i].w); sml = min(sml, mp[i].w); if(mp[i].w < R) { smlr = max(smlr, mp[i].w); } r = v; break; } } } } while(l != r) { for(int i = h[r]; i; i = mp[i].nxt) { int v = mp[i].v; if(tr[v].lev < tr[r].lev) { big = max(big, mp[i].w); sml = min(sml, mp[i].w); r = v; if(mp[i].w < R) { smlr = max(smlr, mp[i].w); } break; } } for(int i = h[l]; i; i = mp[i].nxt) { int v = mp[i].v; if(tr[v].lev < tr[l].lev) { big = max(big, mp[i].w); sml = min(sml, mp[i].w); l = v; if(mp[i].w < R) { smlr = max(smlr, mp[i].w); } break; } } } } signed main () { scanf("%d", &n); for(int i = 1; i < n; i++) { scanf("%d%d%d", &U, &V, &w); add(U, V, w); add(V, U, w); } build(1, 0, 1); scanf("%d", &m); for(int i = 1; i <= m; i++) { scanf("%d%d%d", &U, &V, &R); big = 0; sml = 1e10; smlr = 0; solve(U, V); // printf("%d %d ", big, sml); if(R >= big) { printf("%d\n", R - big); }else if(R < sml) { printf("%d\n", R); }else { printf("%d\n", R - smlr); } } return 0; }