Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51515 AK2022071336 树上博弈 C++ 运行超时 0 1000 MS 12732 KB 2040 2022-07-13 11:49:43

Tests(0/20):


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


测评信息: