Noip2015 D2T3 运输计划【LCA+树上前缀和+二分】
二分后贪心判断。
树上前缀和:(u->v)==> s[u]++, s[v]++, s[lca(u,v)]-=2
最后逆dfs序相加即可。
uoj上要卡常数
#150. 【NOIP2015】运输计划 | TonyFang | 100 | 1780ms | 102412kb |
# include <stdio.h> # include <algorithm> # include <string.h> # include <cctype> # define max(a,b) ((a)>(b)?(a):(b)) // # include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 300010, M = 700010, logN = 19; int head[N], next[M], to[M], w[M], tot=0; int fa[N][logN+1], dep[N], n, m; int LCA[M], Fr[M], To[M], ndfn[N], dfn[N], DFN=0; ll dis[M], s[N]; ll g[N][logN+1]; int _lca; ll _dis; inline int read() { char ch = getchar(); int tx = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) { tx = (tx<<3) + (tx<<1) + ch - '0'; ch = getchar(); } return tx; } inline int add(int u, int v, int _w) { ++tot; next[tot] = head[u]; head[u] = tot; to[tot] = v; w[tot] = _w; } inline void dfs(int x, int fat, int depth) { fa[x][0] = fat; dep[x] = depth; for (int i=1; i<=logN; ++i) { fa[x][i] = fa[fa[x][i-1]][i-1]; g[x][i] = g[fa[x][i-1]][i-1] + g[x][i-1]; } for (int i=head[x]; i; i=next[i]) { if(to[i] == fat) continue; g[to[i]][0] = w[i]; dfs(to[i], x, depth+1); } dfn[x] = ++DFN; ndfn[DFN] = x; } inline void lca(int u, int v) { ll ans = 0; if(dep[u] < dep[v]) swap(u, v); for (int i=logN; i>=0; --i) if((dep[u] - dep[v]) & (1<<i)) { ans += g[u][i]; u = fa[u][i]; } if(u == v) { _lca = u; _dis = ans; return ; } for (int i=logN; i>=0; --i) if(fa[u][i] != fa[v][i]) { ans += g[u][i]; u = fa[u][i]; ans += g[v][i]; v = fa[v][i]; } ans += (g[u][0] + g[v][0]); _lca = fa[u][0]; _dis = ans; return ; } inline bool check(ll x) { memset(s, 0, sizeof(s)); int all = 0; for (int i=1; i<=m; ++i) { if(dis[i] > x) { s[Fr[i]] ++; s[To[i]] ++; s[LCA[i]] -= 2; ++all; } } for (int i=1; i<=n; ++i) s[fa[ndfn[i]][0]] += s[ndfn[i]]; ll mx=0; for (int i=1; i<=n; ++i) if(s[i] == all) mx = max(mx, g[i][0]); for (int i=1; i<=m; ++i) if(dis[i] - mx > x) return false; return true; } int main() { n = read(), m = read(); for (int i=1, u, v, _w; i<n; ++i) { u = read(), v = read(), _w = read(); add(u, v, _w); add(v, u, _w); } dfs(1, 0, 1); ll l=-1, r=0, ans=0; for (int i=1; i<=m; ++i) { Fr[i] = read(), To[i] = read(); lca(Fr[i], To[i]); LCA[i] = _lca; dis[i] = _dis; // printf("LCA=%d dis=%lld\n", LCA[i], dis[i]); r = max(r, dis[i]); } while(1) { ll mid = l+r>>1; if(r-l<=3) { for (ll i=l; i<=r; ++i) if(check(i)) { ans = i; break; } break; } if(check(mid)) r=mid; else l=mid; } printf("%lld\n", ans); return 0; }