C++(g++ 7.5.0) 解法, 执行用时: 32ms, 内存消耗: 5472K, 提交时间: 2022-12-30 10:17:05

#include<iostream>
#include<cstdio>
#include<cmath>
const int maxn=1e5+7;
using namespace std;
int n,x,y,cnt,ans;
int f[maxn],ls[maxn];
struct edge
{
    int y,op,next;
}g[maxn*2];
void add(int x,int y)
{
    g[++cnt]=(edge){y,1,ls[x]};
    ls[x]=cnt;
    g[++cnt]=(edge){x,0,ls[y]};
    ls[y]=cnt;
}
void dfs(int x,int fa,int op)
{
    int num1=0,num2=0;
    for(int i=ls[x];i>0;i=g[i].next)
    {
        int y=g[i].y;
        if(y==fa) continue;
        dfs(y,x,g[i].op);
        if(!g[i].op) num1+=max(f[y],1);
        else num2+=max(f[y],1);
    }
    if(num1>num2)
    {
        ans+=num2;
        if(op) ans+=num1-num2;
        else f[x]=num1-num2;
    }
    else
    {
        ans+=num1;
        if(op) f[x]=num2-num1;
        else ans+=num2-num1;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        x++,y++;
        add(x,y);
    }
    dfs(1,0,0);
    ans+=f[1];
    printf("%d\n",ans);
}

C++(clang++ 11.0.1) 解法, 执行用时: 79ms, 内存消耗: 5540K, 提交时间: 2023-07-29 17:41:15

#include<bits/stdc++.h>
using namespace std;
int n,x,y,tot,a[100005],b[100005],ans;
struct edge
{
	int to;
	int next;
	int head;
	int signal;
}edges[100005<<1];
void add(int x,int y,int opt)
{
	tot++;
	edges[tot].to=y;
	edges[tot].next=edges[x].head;
	edges[x].head=tot;
	edges[tot].signal=opt;
}
void dfs(int x,int fa)
{
	for(int i=edges[x].head;i;i=edges[i].next)
	{
		int v=edges[i].to;
		if(v==fa) 
		{
			continue;
		}
		dfs(v,x);
		if(edges[i].signal)//看能传递哪一部分，另外一部分计入答案
		{
			ans+=a[v];
			b[x]+=max(b[v],1);
		}
		else
		{
			ans+=b[v];
			a[x]+=max(a[v],1);
		}
	}
	int t=min(a[x],b[x]);//优先在内部连边
	a[x]-=t;
	b[x]-=t;
	ans+=t;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		add(x+1,y+1,1);
		add(y+1,x+1,0);
	}
	dfs(1,0);
	cout<<ans+max(a[1],b[1]);
	return 0;
}