Cover the Tree (dfs序)
链接:https://ac.nowcoder.com/acm/contest/5667/C
题目大意:
给定一颗n个节点的无根树,任意两个结点(可叶子也可根节点)可形成一条链,让你用最少的链经过树上所有的边,然后输出这几条链的两边端点。
*一开始看完这道题想的是要求树的直径,然后把未在直径的叶子节点两两配对,后来一想是错的,因为是要遍历所有的边而不是点,这样有大概率有遗漏。*
回到该题上来,思索一下不难发现,如果有x叶子节点的话,那么**最少子链就是(x/2)向上取整个.
就是要求dfs序,然后根左子树的叶节点和根右子树的叶节点一一配对,如果叶节点是奇数个的话,再任意找一个节点与之配对即可。
下面上图
如若按红线匹配的话(任意叶节点匹配),则出现了1-3遗漏
正解:x于x+(n/2)交叉匹配,则不会出现遗漏。然后跑一下dfs序,记录一下叶子节点的出现位置输出即可。
#include <iostream> #include <cstdio> #include<cmath> #include <cstring> #include <algorithm> #include <vector> #include <map> #define inf 9654234 #define ll long long using namespace std; const int maxn=2e5+7; int n; vector ve[maxn],ans; void dfs(int x,int pre){ if(ve[x].size()==1) ans.push_back(x); for(auto it:ve[x]){ if(it==pre) continue; dfs(it,x); } } int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; ve[u].push_back(v); ve[v].push_back(u); } int root=1; while(ve[root].size()==1) root++; dfs(root,-1); int sz=ans.size(); int cnt=(sz+1)/2; cout<<cnt<<endl; if(sz&1) ans.push_back(root); for(int i=0;i<cnt;i++){ cout<<ans[i]<<" "<<ans[i+cnt]<<endl; } return 0; }