当前位置 博文首页 > bjfu170203101的博客:树上 负权直径求法(包括打印路径) 树形

    bjfu170203101的博客:树上 负权直径求法(包括打印路径) 树形

    作者:[db:作者] 时间:2021-09-21 21:04

    思路在代码里。

    总的来说就是,记录每个点往子树,最大距离走哪,次大距离走哪。

    #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
    下一篇:没有了