2020牛客暑期多校训练营(第二场)Cover the Tree
程序员文章站
2024-03-17 08:56:46
...
题目描述
Given an unrooted tree, you should choose the minimum number of chains that all edges in the tree are covered by at least one chain. Print the minimum number and one solution. If there are multiple solutions, print any of them.
输入描述:
输出描述:
连线的话最好是两个叶子节点一连,最后一个点随便连。
于是就要把叶子节点按dfs序标号,然后两个一输出
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200010],b[200020],n,m,i,j,k,l,o,p;
vector<ll> v[200100];
void dfs(ll pos,ll fa)//dfs标号
{
if (a[pos]==1)
{
b[++m]=pos;
return;
}
for (ll i=0;i<v[pos].size();i++)
{
if (v[pos][i]==fa) continue;
dfs(v[pos][i],pos);
}
}
int main()
{
scanf("%lld",&n);
if (n==2)//特判,如果就两个节点直接输出1
{
printf("1\n");
return 0;
}
for (i=1;i<n;i++)
{
ll x,y;
scanf("%lld%lld",&x,&y);
a[x]++;a[y]++;
v[x].push_back(y);
v[y].push_back(x);
}
m=0;
ll root=0;
for (i=1;i<=n;i++)
if (a[i]>1)
{
dfs(i,-1);
root=i;
break;
}
printf("%lld\n",(m+1)/2);
for (i=1;i<=m/2;i++)
printf("%lld %lld\n",b[i],b[m/2+i]);
if (m%2) printf("%lld %lld\n",b[m/2+1],root);
}
然后只有80分。。。
查了之后
发现会被这个图卡住继菊花图后的另一个奇怪的图
然后改一下输出顺序,AC
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200010],b[200020],n,m,i,j,k,l,o,p;
vector<ll> v[200100];
void dfs(ll pos,ll fa)
{
if (a[pos]==1)
{
b[++m]=pos;
return;
}
for (ll i=0;i<v[pos].size();i++)
{
if (v[pos][i]==fa) continue;
dfs(v[pos][i],pos);
}
}
int main()
{
scanf("%lld",&n);
if (n==2)
{
printf("1\n");
return 0;
}
for (i=1;i<n;i++)
{
ll x,y;
scanf("%lld%lld",&x,&y);
a[x]++;a[y]++;
v[x].push_back(y);
v[y].push_back(x);
}
m=0;
ll root=0;
for (i=1;i<=n;i++)
if (a[i]>1)
{
dfs(i,-1);
root=i;
break;
}
printf("%lld\n",(m+1)/2);
for (i=1;i<=m/2;i++)
printf("%lld %lld\n",b[i],b[(m+1)/2+i]);
if (m%2) printf("%lld %lld\n",b[m/2+1],root);
}
推荐阅读
-
2020牛客暑期多校第二场 C - Cover the Tree(思维/贪心)
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客多校第二场C Cover the Tree(dfs序)
-
2020牛客多校第二场C题Cover the Tree
-
2020牛客暑期多校训练营(第一场)D Quadratic Form 拉格朗日乘数法+求矩阵的逆
-
2018牛客网暑期ACM多校训练营第二场 I - car(脑洞)
-
2020牛客暑期多校训练营2
-
2020牛客多校第二场 B.Boundary
-
F Fake Maxpooling(2020牛客暑期多校训练营(第二场))(单调队列)
-
2020牛客暑期多校训练营(第四场)H.Harder Gcd Problem