旅游规划

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2558 字
给定一棵树，输出所有位于某条最长路径上的节点
一本通
练习
正文

/*
原题：旅游规划（一本通 5.2 练习2）
题意：给定一棵树，输出所有位于某条最长路径（直径）上的节点编号，按编号升序每行一个。
思路：两次 BFS 求直径端点 A、B 与直径长 D；对每个点取“连向各邻域的最长分支”中最大的两条，其和等于 D 说明该点在某条直径上。
复杂度：O(n) 时间，O(n) 空间。
易错点：要的是“至少在某条直径上”的并，而非“在所有直径上”的交；深递归易爆栈，用 BFS。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
vector<int> g[N];
int parent[N],down[N],up[N],mx1[N],mx2[N],mx1c[N];
int bfs(int s,vector<int>& d,int n){
    fill(d.begin(),d.begin()+n,-1);
    queue<int> q;
    q.push(s);
    d[s]=0;
    int far=s;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v:g[u])
            if(d[v]<0){
                d[v]=d[u]+1;
                q.push(v);
                if(d[v]>d[far])far=v;
            }
    }
    return far;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> d0(n),dA(n);
    int A=bfs(0,d0,n);
    int B=bfs(A,dA,n);
    int D=dA[B];
    vector<int> order;
    vector<bool> vis(n,false);
    queue<int> q;
    q.push(0);
    vis[0]=true;
    parent[0]=-1;
    while(!q.empty()){
        int u=q.front();q.pop();
        order.push_back(u);
        for(int v:g[u])
            if(!vis[v]){
                vis[v]=true;
                parent[v]=u;
                q.push(v);
            }
    }
    for(int i=n-1;i>=0;i--){
        int u=order[i];
        down[u]=0;
        for(int v:g[u])
            if(v!=parent[u])down[u]=max(down[u],1+down[v]);
    }
    for(int i=0;i<n;i++){
        int u=order[i];
        mx1[u]=mx2[u]=0;
        mx1c[u]=-1;
        for(int v:g[u])
            if(v!=parent[u]){
                int val=1+down[v];
                if(val>mx1[u]){
                    mx2[u]=mx1[u];
                    mx1[u]=val;
                    mx1c[u]=v;
                }else if(val>mx2[u])mx2[u]=val;
            }
    }
    up[0]=0;
    for(int i=0;i<n;i++){
        int u=order[i];
        if(u==0)continue;
        int p=parent[u];
        int best_sib=(mx1c[p]==u)?mx2[p]:mx1[p];
        up[u]=1+max(up[p],best_sib);
    }
    vector<int> ondia;
    for(int x=0;x<n;x++){
        int b1=up[x],b2=0;
        for(int v:g[x])
            if(v!=parent[x]){
                int val=1+down[v];
                if(val>b1){
                    b2=b1;
                    b1=val;
                }else if(val>b2)b2=val;
            }
        if(b1+b2==D)ondia.push_back(x);
    }
    sort(ondia.begin(),ondia.end());
    for(int x:ondia)cout<<x<<"\n";
    return 0;
}
旅游规划

正文

一本通·提高篇的其它内容
