P8578 [CoE R5] So What Do We Do Now?

wflengxuenong · 2022-11-08 09:46:08 · 个人记录

构造题，dfs序可以使得差值最小。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
vector<int>t[N];
int n,dfn[N],u,v;
long long ans;
void dfs(int u,int fa){
    dfn[u]=++id;
    for(auto v:t[u]){
        if(v==fa)continue;
        dfs(v,u);
    }   
}

int main(){
    memset(din,63,sizeof(din));
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        t[u].push_back(v) ;
        t[v].push_back(u);  
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)cout<<dfn[i]<<" ";
}