Noip2015 D2T3 运输计划【LCA+树上前缀和+二分】

tonyfang posted @ 2016年10月18日 23:13 in NOIP with tags c++ OI , 346 阅读

二分后贪心判断。

树上前缀和:(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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter