当前位置 博文首页 > bjfu170203101的博客:树上 负权直径求法(包括打印路径) 树形
思路在代码里。
总的来说就是,记录每个点往子树,最大距离走哪,次大距离走哪。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e5+7;
int head[M],cnt;
void init(){cnt=0,memset(head,0,sizeof(head));}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
int vs[M],f[M][2],vis[M];//f[i][0]从i点开始,往i为根的子树最远的距离,f[i][1]为次远的距离
//f[i][0]+f[i][1]最大的值即直径
int p,q,mx=-1;
int nxt2[M],nxt1[M];
//nxt1[i]某个点i,从i点开始,往i为根的子树最远的距离的路径,下一步走哪。
//nxt2[i]同理为次远距离下一步走哪
void dfs(int x,int fa)
{
for(int i=head[x];i;i=ee[i].nxt)
{
int y=ee[i].to;
if(y==fa) continue;
dfs(y,x);
if(f[y][0]+1>f[x][0]) f[x][1]=f[x][0],nxt2[x]=nxt1[x],nxt1[x]=y,f[x][0]=f[y][0]+1;
else if(f[y][0]+1>f[x][1]) f[x][1]=f[y][0]+1,nxt2[x]=y;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
add(u,v,1);
add(v,u,1);
}
dfs(1,0);
int id=0,x,p,q;
for(int i=1;i<=n;++i) if(f[i][0]+f[i][1]>f[id][0]+f[id][1]) id=i;//找到直径上的点(即两条链的交点)
vis[id]=true,vis[x=nxt1[id]]=true,p=x;
while(nxt1[x]) vis[x=nxt1[x]]=true,p=x;//往最大距离走 ,最后标记的点即端点
vis[x=nxt2[id]]=true,q=x;//往次大距离走
while(nxt1[x]) vis[x=nxt1[x]]=true,q=x;//次大只需要第一步是次大,后面都是最大
cout<<p<<" "<<q<<endl;//直径端点
for(int i=1;i<=n;i++)//标记直径上的点
if(vis[i])cout<<i<<" ";
cout<<endl;
return 0;
}
?
cs