P2680 [NOIP2015 提高组] 运输计划

题目

公元 $2044$ 年，人类进入了宇宙纪元。

L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$，任意飞船驶过它所花费的时间为 $t_j$，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？
对于 $100\%$ 的数据，保证：$1 \leq a_i,b_i \leq n$，$0 \leq t_i \leq 1000$，$1 \leq u_i,v_i \leq n$。

题解

首先提炼出题目要求——最大值最小 想到二分最大值
想一想二分之后如何判断是否合法
把大于 最大值 的路径都选出来，在树上标记出来
如果有一个边被选出来的所有路径都包括，且这其中最长的路径减去 边权小于 二分值，那么就合法，否则就不

实现问题

把大于 最大值 的路径都选出来

路径长度可以用树上前缀和

把大于 最大值 的路径都选出来，在树上标记出来

树上差分

出现的问题

1.二分写错
2.要用upper_bound
3.二分测试没全部初始化

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 100;
int head[N], nxt[N << 1], edge[N << 1], to[N << 1], cnt = 1;

int point_to_edge[N];

int n, m;

int longest_path;
struct U
{
	int m, n, length;

	bool operator < (const U o) const
	{
		return length < o.length;
	}
} u[N];
 

// <lca>

int anc[N][21], depth[N];

void lca_init()
{
	for(int j = 1; j <= 20;j++)
	{
		for(int i = 1;i <= n;i++)
		{
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
		}
	}
}

int lca_query(int x, int y)
{
	if(depth[x] < depth[y])
		swap(x, y);



	for(int j = 20;j >= 0;j--)
	{
		if(depth[anc[x][j]] >= depth[y])
		{
			x = anc[x][j];
		}
	}

	if(x == y) return x;
	for(int j = 20;j >= 0;j--)
	{
		if(anc[x][j] != anc[y][j])
		{
			x = anc[x][j], y = anc[y][j];
		}
	}
	return anc[x][0];
}
// </lca>

// <预处理前缀和+lca>

int sum[N];
void dfs_sum(int u, int fa)
{
	depth[u] = depth[fa] + 1;
	anc[u][0] = fa;
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		point_to_edge[v] = i;
		sum[v] = sum[u] + edge[i];
		dfs_sum(v, u);
	}
}

// </预处理前缀和>


// <快读> 
int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

// </快读>



void add(int x, int y, int z)
{
	to[++cnt] = y;
	edge[cnt] = z;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

// <check>

// <树上差分>

int differ[N], sum_differ[N];
int best_can_edge_quan = 0;


void dfs_differ(int u, int fa, int T)
{
	sum_differ[u] += differ[u];
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs_differ(v, u, T);
		sum_differ[u] += sum_differ[v];
	}
	if(sum_differ[u] == (m - T + 1) && best_can_edge_quan < edge[point_to_edge[u]])
	{
		best_can_edge_quan = edge[point_to_edge[u]];
	}

//	cout << "qwq "<<u <<" "<< sum_differ[u] << endl;
}

// </树上差分>

bool check(int T)
{
	best_can_edge_quan = 0;
	memset(differ, 0, sizeof(differ));
	memset(sum_differ, 0, sizeof(sum_differ));


	U temp;
	temp.m = temp.n = 0;
	temp.length = T;
	int first_bad_order = upper_bound(u + 1, u + 1 + m/*!!!*/, temp) - u;
	if(temp.length >= u[first_bad_order].length && first_bad_order == m) return 1;

//	cout << "qwq"<<first_bad_order << endl;
//	cout << first_bad_order << endl;
	for(int i = first_bad_order;i <= m;i++)
	{
		differ[u[i].m]++, differ[u[i].n]++, differ[lca_query(u[i].n, u[i].m)] -= 2;
	}

	dfs_differ(1, 0, first_bad_order);


//	cout << "qwq" << best_can_edge_quan << endl;
	if(longest_path - best_can_edge_quan <= T)
	{
		return 1;
	}
	return 0;
}

// </check>


int binary_search(int r)
{
	int l = 0;

	while(l < r)
	{
		int mid = (l + r) >> 1;
//		cout << mid << endl;
		if(check(mid)/*可行*/)
		{
			r = mid; 
//			cout << mid << " ok" << endl;
		}
		else
		{
			l = mid + 1;
//			cout << mid << " n" << endl;
		}
	}
	return l;
}

int main()
{
	n = read(), m = read();

	int x, y, z;
	for(int i = 1;i <= n - 1;i++)
	{
		x = read(), y = read(), z = read();
		add(x, y, z), add(y, x, z);
	}
	dfs_sum(1, 0);
	lca_init();



	for(int i = 1;i <= m;i++)
	{
		u[i].m = read(), u[i].n = read(), u[i].length = sum[u[i].n] + sum[u[i].m] - 2 * sum[lca_query(u[i].n, u[i].m)];
		longest_path = max(longest_path, u[i].length);
	}

	sort(u + 1, u + 1 + m);

	printf("%d\n", binary_search(longest_path));

//	differ[2] ++, differ[6] ++, differ[4] ++,differ[1] -= 2;
//
//	dfs_differ(1, 0, 0);
//	cout << sum_differ[1]; 
//	cout << edge[point_to_edge[3]];
	return 0;
}

其实树上差分合树上前缀和可以优化，不用递归