树网的核

发表于 | 更新于 | 分类于 ， ，

偏门的知识点,但是很好玩啊

前置知识

树的直径

定义:

树上最长的链

适用范围:

显然:树

求解方式:

  • 从任意一个点DFS并且存下到每个点到这个点的距离
  • 然后从距离最远的那个点又DFS一遍,这次找到的最大的距离就是直径

:但是,还有一个问题:怎么存下来直径上的每一个点(任意一条)

  • 其实也很简单,在第二遍的DFS时保存每个点的Father
  • 然后从最后找到的那个远点一直找Father并且把每个点统计起来就是了

算法主体

问题描述

给定一颗树(无根)

求一条路径,使得其他点到这条路径的最大距离最小$(n<=300000)$,并且使得这条路径的长度$\le s$

算法分析

暴力

呵呵

分析一波

显然,这条路径肯定在直径上(感性证明)

然后呢?

  • 直径上每一个点记能延伸出去的最长距离为$f[x]$

那么显然,对于选定路径x到y:

我们定义:$u\in(x,y)$,$s$为直径起点,$t$为直径终点

于是我们就得到了$n^2$的算法

然而:$n<=300000$

所以我们需要一个$O(n)$的算法

最终算法

其实很简单,我们有两个优化:

优化1：

我们不需要与每一个$f[u]$比较,而是直接与所有$f[u]$的最大值$fmax$比较

然而正确性？

设

  • $fmax$是由点$p$延伸出来的

  • $s,t$分别是直径的起点与终点

那么我们可以分为两种情况:

况1:

$p\in(x,y)$

这很显然正确,因为它和之前没有任何区别

况2:

$p\notin(x,y)$

这个时候明显$len(s,x)\ge fmax$或$len(y,t)\ge fmax$

为什么?

我们采用反证

假设$len(s,x)\le fmax$或$len(y,t)\le fmax$

那么明显直径应该以延伸到$fmax$那一条链上,假设不成立

综上:

我们可以直接和$fmax$比较,而不是每次都和$n$个比较

得证:)

优化2:

明显当一条链延长的时候它的解只可能变得更优

证明就免了吧

经过$sun123zxy$的反复询问我还是把证明写出来吧:

况1:

当前的最大值是从$x$或$y$并且在直径上扩展出去的

那么当我们扩展的时候$len(s,x)$与$len(y,t)$中的一项必然变小(否则你就没有扩展啊)

况2:

当前的最大值是$fmax$而反观我们的式子$max(fmax,len(s,x),len(x,t))$

当我们扩展的时候$len(s,x)$与$len(y,t)$中的两项不会由任何一项变大,所以最大值仍为$fmax$

综上:

当我们扩展这条链时,答案显然不会变得更劣

得证:)

于是我们就可以直接用两个指针在$O(n)$的时间复杂度内实现路径的枚举

代码

代码框架:

  • 前向星
  • DFS求直径
  • 通过爬father的过程来找直径上的具体点
  • 然后同时使用两个指针维护枚举路径

具体实现:

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
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define bl bool
#define mem(a) memset(a,0,sizeof(a))
#define maxn 500005
#define maxm 2000005
#define inf 0x7fffffff
using namespace std;
ll Min(ll x,ll y){if(x<y)return x;return y;}
ll Max(ll x,ll y){if(x>y)return x;return y;}
ll read(){
	ll s=0,h=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')h=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
	return s*h;
}
ll n,s,cnt,h[maxn],ff,tt,le,rt,dis,f[maxn],now,Fmax,bian[maxn];
vector<ll>r;bl flg[maxn];
struct Edge{ll f,t,l,next;}e[maxm];
void add(ll f,ll t,ll l){e[++cnt]={f,t,l,h[f]};h[f]=cnt;}
void madd(ll f,ll t,ll l){add(f,t,l);add(t,f,l);}
void Getr(ll u,ll fa,ll d){
	f[u]=fa;ll v;
	if(d>dis){dis=d;rt=u;}
	for(int i=h[u];i;i=e[i].next){
		v=e[i].t;if(v==fa)continue;
		Getr(v,u,d+e[i].l);
	}
}
void GetR(ll u){
	while(f[u]){r.push_back(u);u=f[u];flg[u]=1;}
	r.push_back(u);flg[u]=1;
}
void Dfs(ll u,ll fa,ll l){
	ll v;Fmax=Max(Fmax,l);
	for(int i=h[u];i;i=e[i].next){
		v=e[i].t;if(v==fa)continue;
		if(flg[v])Dfs(v,u,0),bian[u]=e[i].l;
		else Dfs(v,u,l+e[i].l);
	}
}
int main(){
	n=read();s=read();
	for(int i=1;i<n;i++){
		ff=read();tt=read();le=read();
		madd(ff,tt,le);
	}
	dis=0;rt=0;
	Getr(1,0,0);
	dis=0;mem(bian);
	Getr(rt,0,0);
	GetR(rt);
	Dfs(rt,0,0);
	ll p1=0,p2=0,len=0,L=0,ltot=0,ans=inf;
	for(int i=0;i<r.size();i++)ltot+=bian[r[i]];
	while(p2<=r.size()){
		while(1){
			if(len+bian[r[p2]]<=s&&p2<r.size()-1){
				len+=bian[r[p2]];
				p2++;	
			}
			else break;
		}
		ans=Min(ans,Max(L,ltot-len-L));
		len-=bian[r[p1]];
		L+=bian[r[p1]];
		p1++;p2=Max(p1,p2);
	}
	ans=Max(ans,Fmax);
	cout<<ans<<endl;
	return 0;
}

温馨提示:fmax为一个库函数名

例题:

(luogu)P1099-树网的核

(luogu)P2491-[SDOI2011]消防

就是一道题,也只有一道模板题

个人认为这个知识点很难考

因为这个知识点一旦需要套,那么就明显需要知道具体哪条路径

然而这样你就没法优化了啊(实际上优化2能用)

完:)