7.27T2

发布时间：2020-12-14 05:12:02 所属栏目：大数据来源：网络整理

导读：不可做题 sol：首先有个很显然的性质就是答案一定是在叶子上最优，然后画画图发现就是从最底层看，如果一条链就看做一个点，向上的第一颗非链的节点，它的儿子数-1就会对答案贡献，所有这样的累加起来就是答案了实现挺容易的，记一个数组bo[i]表示i是否是链

不可做题

sol：首先有个很显然的性质就是答案一定是在叶子上最优，然后画画图发现就是从最底层看，如果一条链就看做一个点，向上的第一颗非链的节点，它的儿子数-1就会对答案贡献，所有这样的累加起来就是答案了

实现挺容易的，记一个数组bo[i]表示i是否是链，XJB搞搞就可以了

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0; bool f=0; char ch=‘ ‘;
    while(!isdigit(ch)) {f|=(ch==‘-‘); ch=getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0) {putchar(‘-‘); x=-x;}
    if(x<10) {putchar(x+‘0‘); return;}
    write(x/10); putchar((x%10)+‘0‘);
}
#define W(x) write(x),putchar(‘ ‘)
#define Wl(x) write(x),putchar(‘n‘)
const int N=1000005,M=2000005;
int n,ans=0;
int deg[N],tot=0,Next[M],to[M],head[N];
bool bo[N];
inline void Link(int x,int y)
{
    Next[++tot]=head[x]; to[tot]=y; head[x]=tot; deg[y]++;
}
inline void dfs(int x,int fat)
{
//    cout<<"x="<<x<<‘ ‘<<"fat="<<fat<<endl;
    int e,sum=0;
    bool flg=1;
    bo[x]=1;
    for(e=head[x];e;e=Next[e]) if(to[e]!=fat)
    {
        if(flg)flg=0; else bo[x]=0;
        dfs(to[e],x);
        if(!bo[to[e]])bo[x]=0; else sum++;
    }
    if(sum>0) ans+=sum-1;
}
int main()
{
    freopen("iiiiiii.in","r",stdin);
    freopen("iiiiiii.out","w",stdout);
    int i,x,y;
    R(n);
    if(n==1) return puts("0"),0;
    for(i=1;i<n;i++)
    {
        R(x); R(y); Link(x,y); Link(y,x);
    }
    for(i=1;i<=n;i++) if(deg[i]>2) {dfs(i,0); Wl(ans); return 0;}
    puts("1");
    return 0;
}

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!