洛谷P2680 树上路径，差分，二分答案

题意：

给出一棵有$n$个结点的树，有$m$个人，同时从某个地方$u_i$出发，去往另一个地方$v_i$。可以选择一条边，使得这条边的长度为$0$，问最早什么时候能让所有人都到达终点？

Solution：

即需要让这$m$个花费时间的最大值最小，我们可以二分答案，二分一个时间$t$，看是否在时间$t$之内，让所有人到达终点，这是有二分单调性的，一般来说，二分的不是具体数值，而是一类具有”至少“，”至多“这样特性的东西，此处二分的即最多$x$时间，能否让所有人都到达终点，找到第一个符合条件的$x$就是答案

接下来考虑如何$check$，如果需要所有路径都在$x$时间内到达目的地，至少原本需要的时间$t\le x$的一定是可以做到的，只需要考虑$t>x$的路径，由于只能选择一条路径，所以我们需要找出他们是否存在交集，这可以通过路径覆盖得到，路径覆盖又可以通过树上差分实现。假设$t>x$的路径有$k$条，只需要找到一条边，使得经过这条边的路径数为$k$，并且删去这条边能让最长的那条道路在$x$时间内到达，那么所有道路都可以到达，否则，找不到一条符合这个条件的边，就不可能实现在$x$时间内都到达了

需要找出他们中大于$x$的部分和最长的那条路径，先排序是个不错的常熟优化的选择，时间复杂度为$O((n+m)logC)$，$C$为二分长度

// #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=300005,inf=0x3fffffff;
const long long INF=0x3f3f3f3f3f3f,mod=1e9+7;

struct node
{
	int u,v,dis,x;
}a[N];

struct way
{
	int to,next,w;
}edge[N<<2];
int cntt,head[N<<1];

void add(int u,int v,int w)
{
	edge[++cntt].to=v;
	edge[cntt].w=w;
	edge[cntt].next=head[u];
	head[u]=cntt;
}

int n,m,f[N<<1][21],depth[N<<1],sum[N<<1],tot,belong[N<<1];

void dfs1(int u,int fa)
{
	f[u][0]=fa; depth[u]=depth[fa]+1;
	for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to,w=edge[i].w;
		if(v==fa) continue;
		sum[v]=sum[u]+w;
		dfs1(v,u);
	}
}

int lca(int x,int y)
{
	if(depth[x]<depth[y]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(depth[f[x][i]]>=depth[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

int dis(int x,int y,int& tmp){return sum[x]+sum[y]-2*sum[tmp=lca(x,y)];}

int del[N<<1],val[N<<1];

void dfs(int u,int fa)
{
	val[u]=del[u];
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		val[u]+=val[v];
	}
}

bool check(int x)
{
	int cnt=0;
	for(int i=1;i<=m;i++)
	{
		if(a[i].dis>x)
		{
			auto& [u,v,dis,x]=a[i]; cnt++;
			del[u]++; del[v]++; del[x]--; del[f[x][0]]--;
		}
		else break;
	}
	dfs(1,0);
	auto initial=[&]()
	{
		for(int i=1;i<=m;i++)
		{
			if(a[i].dis>x)
			{
				auto& [u,v,dis,x]=a[i];
				del[u]--; del[v]--; del[x]++; del[f[x][0]]++;
			}
			else break;
		}
	};
	for(int i=n+1;i<=tot;i++)
	{
		if(val[i]==cnt&&a[1].dis-belong[i]<=x)
		{
			initial();
			return true;  
		}
	}
	initial();
	return false;
}

int read()
{
	int ret=0,base=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-') base=0;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		ret=ret*10+ch-48;
		ch=getchar();
	}
	return base?ret:-ret;
}

int main()
{
	n=tot=read(); m=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		belong[++tot]=w;
		add(u,tot,w); add(tot,u,w);
		add(v,tot,0); add(tot,v,0);
	}
	dfs1(1,0);
	for(int i=1;i<=m;i++)
	{
		auto& [u,v,dis,x]=a[i];
		u=read(); v=read(); dis=::dis(u,v,x);
	}
	sort(a+1,a+1+m,[&](const node& x,const node& y){
		return x.dis>y.dis;
	});
	int l=0,r=inf,ans;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172