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

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

二分后贪心判断。

树上前缀和:(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;
}
Kar PUC Chemistry Mo 说:
2022年9月19日 21:57

Karnataka state Pre University Education 1st and 2nd year PUE students can download Kar PUC-I, PUC-II Chemistry Question Paper 2023 with answer solutions for Kannada medium and English medium regular, term, and annual final public March 2023 examination tests provided by subject experts of PUE and DKPUCPA to both paper-1 & paper-2 exams. Kar PUC Chemistry Model Paper Every year KAR PUE and Dakshina Kannada Pre-University Colleges Principals’ Association (DKPUCPA) is announced subject wise study material with practice mock test question bank in Set wise for general and vocational course Arts, Science and Commerce stream government and private college students of the state, and KAR 1st and 2nd PUC Chemistry Model Paper 2023 is announced with answer solutions for both.

jnvstresults.in 说:
2023年4月19日 16:21

The JNV Class Selection tests are conducted for admissions in 661 JNV Schools in all regions or zones under NVS. Those students who have appeared on the admission selection test are waiting for JNVST Resulte date. In this guide, we will help you to know about Navodaya Result Date along with jnvstresults.in the Selected list and Waiting list download available dates here. We primarily use Google ad sense ads on our website. We do not use extensive ads on our website.

jnanabhumiap.in 说:
2024年1月12日 22:19

JNANABHUMI AP provides a CBSE syllabus for all classes for the academic year 2024 has been designed as per the guidelines of the CBSE Board. The syllabus offers a conceptual background and lays the groundwork for the Class 10 Board exams. jnanabhumiap.in By visiting the page, students will find the downloadable pdf of the reduced CBSE 10th Syllabus along with the deleted portion of the syllabus for each subject. So, students are advised to prepare for the exam, as per the syllabus mentioned here.


登录 *


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