CSAcademy Round#65(Div.2 only) Crossing Tree

题目链接https://csacademy.com/contest/round-65/task/crossing-tree/

题意:给一棵树,可以从任意点出发,找一条最短的路,使之覆盖所有的边,边可以重复走。

思路:考虑到如果从一个点出发最后回到这个点,那么就相当于DFS遍历一颗树一样,最后每条边都走过两遍,即长度为2* (n-1),然而根据题目要求我们得知最后不用回到原点,那么我只要让最后一条返回原点的边尽可能的长即可,而这个就等价于找树的直径,至此问题就解决了,输出方案只要每次先不要沿着包含树的直径的端点的子树DFS即可。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
template <class T1, class T2>inline void gmax(T1 &a,T2 b){if (b>a) a=b;}
template <class T1, class T2>inline void gmin(T1 &a,T2 b){if (b<a) a=b;}
int n,u,v,mx=-1,mxroot[2],dfs_clock,dep[maxn],L[maxn],R[maxn];
vector<int>G[maxn];
queue<int>Q;
bool intree(int u,int f){
    return (L[u]<=L[f] && R[f]<=R[u]);
}
void dfs(int u,int f,int k){
    dep[u]=f==0?0:dep[f]+1;
    if (k==1) L[u]=++dfs_clock;
    if (mx<dep[u]){
        mx=dep[u];
        mxroot[k]=u;
    }
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u,k);
    }
    if (k==1) R[u]=dfs_clock;
}
bool flag;
void dfs2(int u,int f){
    if (u==mxroot[1]){
        flag=true;
        return;
    }
    int pos=0;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        if (intree(v,mxroot[1])) pos=v;
        else{
            Q.push(v);
            dfs2(v,u);
            Q.push(u);
        }
    }
    if (pos){
        Q.push(pos);
        dfs2(pos,u);
        if (flag) return;
        Q.push(u);
    }
}
int main(){
    read(n);
    for (int i=1;i<n;i++){
        read(u),read(v);
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1,0,0);
    mx=-1;
    dfs(mxroot[0],0,1);
    Q.push(mxroot[0]);
    dfs2(mxroot[0],0);
    printf("%d\n",(int)Q.size()-1);
    while (!Q.empty()){
        printf("%d ",Q.front());
        Q.pop();
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注