不会树形dp的同学看过来
不会树形dp的同学有福了,不过我不是给大家介绍树形dp的解法,因为我看题解区大佬们树形dp讲的太好了,我再讲一遍树形dp就没意义了。而且我也是第一次学树形dp,然后在听课的之前,想自己先尝试一下,就有了我这个解法。
进入正题。
相信你们肯定会写最简单的dfs:
void dfs(int u,int most)
{
st[u]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
dfs(j,most+w[i]);
}
}
}
那么这里我将教大家如何用四次最简单的dfs解决这个问题。
其实这个题有一个结论,树的中心一定在树的直径上面。(很容易证明,因为树的直径是树上最长的一条路径,那么想要达到树的中心的目的,那就必须在树的直径上面,证的比较敷衍,大家可以画个图理解一下)
我们就运用这个结论,来寻找我们的答案。
首先我们要做的第一件事就是找到树的直径的两个端点,这个过程可以利用两次dfs来解决:
- 第一次dfs从任意起点开始,走到一个距离最远的点,那就是树的直径的一个端点
- 第二次dfs再从第一次dfs找到的一个端点开始,继续找到一个距离最远的点,那就是树的直径的另外一个端点。
这里我就不赘述证明了,想看证明的同学可以移步洛谷里面一个题的题解,里面有证明: 传送门
现在我们找到了树的直径的两个端点,然后分别求一下树上的每个点距离这两个端点的距离,还是dfs。这里看起来需要两次dfs,其实只需要在进行一次即可,因为我们在上面的第二次dfs里面,就可以顺带求出每个点距离第一个端点的距离。所以这里我们只需要dfs第二个端点就可以了。
最后一次dfs,我们枚举一下树上的点,为什么要枚举树上的点呢?不是枚举树的直径上的点就够了吗?
当然是这样,但是要做到只枚举树的直径上的点其实有点难做到,而且枚举树上的所有点复杂度也只是O(n)而已,所以大可不必去优化他。
那么最后一次dfs的时候,我们就更新一下最小的最大长度就可以了,具体更新方程就是 len=min(len,max(d1[u],d2[u])),其实也有点像dp,哈哈。
d1[u] 和 d2[u] 分别表示当前点分别距离两个端点的距离。上面那个转移方程可以只针对在树的直径上的点去理解,会更好理解一些。(因为如果一个点不在树的直径上,那么这个值会更大,不用考虑它)
好了,下面就是四次dfs的代码了,时间复杂度 O(n),跑完大概35ms。(鄙人比较喜欢偷懒,所以代码比较丑)
代码看起来很长,其实有效部分很短,因为我比较喜欢偷懒~~
#pragma GCC diagnostic error "-std=c++11"
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<cmath>
#include<climits>
#define in(x) x=read()
#define out(x) printf("%d\n",x);
#define f(x,a,b,c) for(int x=a;x<=b;x+=c)
#define in2(x,y) scanf("%d%d",&x,&y);
#define in3(x,y,z) scanf("%d%d%d",&x,&y,&z);
#define in4(x,y,z,v) scanf("%d%d%d%d",&x,&y,&z,&v);
#define out2(a,b) printf("%d %d\n",a,b);
#define out3(a,b,c) printf("%d %d %d\n",a,b,c);
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d);
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int N=1e4+10,M=2*N,mod=23333333;
int n,m,k,s;
int index1,index2,maxv,len;
int d1[N],d2[N];
inline int read() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
int h[N],e[M],ne[M],idx,w[M],st[N];
void add(int h[],int a,int b,int c)
{
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
void dfs1(int u,int most)//第一次dfs求直径的第一个端点
{
st[u]=1;
if(most>maxv)
{
maxv=most;
index1=u;
}
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
dfs1(j,most+w[i]);
}
}
}
void dfs2(int u,int most)//第二次dfs求树的直径的第二个端点+d1[u]
{
st[u]=1;
if(most>maxv)
{
maxv=most;
index2=u;
}
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
d1[j]=most+w[i];
dfs2(j,d1[j]);
}
}
}
void dfs3(int u,int most)//第三次dfs求d2[u]
{
st[u]=1;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
d2[j]=most+w[i];
dfs3(j,most+w[i]);
}
}
}
void dfs4(int u,int most)//第四dfs求 len=min(len,max(d1[u]+d2[u]))
{
st[u]=1;
len=min(len,max(d1[u],d2[u]));
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
dfs4(j,most+w[i]);
}
}
}
int main()
{
in(n);
memset(h,-1,sizeof h);
f(i,1,n-1,1)
{
int a,b,c;
in3(a,b,c);
add(h,a,b,c),add(h,b,a,c);
}
dfs1(1,0);//第一次dfs求第一个端点
memset(st,0,sizeof st);
maxv=0;
dfs2(index1,0);//第二次dfs求第二个端点+d1[u]
memset(st,0,sizeof st);
len=INT_MAX;
maxv=0;
dfs3(index2,0);//第三次dfs求d2[u]
memset(st,0,sizeof st);
dfs4(index1,0);//第四次dfs求 len=min(len,max(d1[u],d2[u]))
out(len);
return 0;
}
码字不易,喜欢就点个赞再走呗~~~
四个 dfs ,这个牛逼
谢谢