HDU5758 Explorer Bo 思维+树形dp

题意自己看题目吧，挺短的。

思考过程：昨天感觉一天不做题很对不起自己，于是晚上跑到实验室打开别人树形dp的博客做了上面最后一个HDU的题，也是个多校题。。一开始没有头绪了很久，因为起点不固定，所以这1e5的数据要跑的话就有很多很多转移，但是状态又不可能定义得很复杂。。然后后来就想到和叶子有关系。就这样停滞不前了很久。半夜看别人博客感觉看懂了，其实也没比没看博客前多懂多少。我只想到了肯定是一个叶子到另一个叶子然后跳一下到另一个叶子然后继续这样做。今天中午又想了很久。首先画样例是关键，学了别人的dp写法后来发现自己样例都不能过。

图一如既往的丑。

反正这个二叉树这样走是8的，然后只跳了一次，并不是网上别人说的什么（叶子+1）/2。。但是确实是叶子和叶子匹配。

我们不难发现有些边走了两次有些边走了一次。而dp的过程也是基于此。首先因为核心在于叶子，所以要以一个非叶子节点开始dfs。

我们考虑一个点u,他的某个儿子v，如果v有偶数个叶子，那么u->v这条边对答案的贡献是2，若为奇数则为1。因为一个有偶数个叶子的儿子肯定是其中某两个叶子去和v的祖先节点或者兄弟节点的叶子匹配最优（所花费的跳最少）。而奇数个时只有一个点需要这样。这个不懂的自己画一画，我也画了很久，太菜了。

如果总共有偶数个叶子，那么显然两两匹配，这就是答案。而若有奇数个叶子节点，就有一个点无法匹配，那么dfs枚举一下就好了。用dp做法就是找一条只有一个叶子的最长链。。不是特别懂。

直接放看得懂的链接吧，喜欢dp写法的自己百度，第一篇就是。

https://www.cnblogs.com/zufezzt/p/5796175.html

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define _mp make_pair
#define db double
#define eps 1e-9
#define inf 1e9
using namespace std;
const int maxn=1e5+7;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int cnt;
int n,m;
int root;
int fir[maxn],nxt[maxn*2],to[maxn*2];
int du[maxn],siz[maxn];
int dp[maxn][2];
void add_e(int x,int y)
{
    ++cnt;nxt[cnt]=fir[x];fir[x]=cnt;to[cnt]=y;
}
void dfs1(int x,int fa)
{
    dp[x][0]=0;dp[x][1]=inf;
    siz[x]=0;
    int ts=0;
    for(int i=fir[x];i;i=nxt[i])
    {
        if(to[i]==fa)continue;
        dfs1(to[i],x);
        siz[x]+=siz[to[i]];
        int d;
        ts++;
        if(siz[to[i]]%2==0)d=2;
        else d=1;
        dp[x][0]+=dp[to[i]][0]+d;
    }
    for(int i=fir[x];i;i=nxt[i])
    {
        if(to[i]==fa)continue;
        if(siz[to[i]]==1&&ts>1)dp[x][1]=min(dp[x][1],dp[x][0]);
        if(dp[to[i]][1]>=inf)continue;
        int k=((siz[to[i]]&1)?1:-1);
        dp[x][1]=min(dp[x][1],dp[x][0]-dp[to[i]][0]+dp[to[i]][1]+k);
    }
    if(ts==0)siz[x]=1;

}
void init()
{
    memset(fir,0,sizeof(fir));
    cnt=0;
    memset(du,0,sizeof(du));
}
int main()
{
    int T;
    T=read();
    while(T--)
    {
        init();
        n=read();
        int p,q;
        for(int i=1;i<n;i++)
        {
            p=read();q=read();
            add_e(p,q);add_e(q,p);
            du[p]++;du[q]++;
        }
        int ss=0;
        root=0;
        for(int i=1;i<=n;i++)
        {
            if(du[i]!=1)root=i;
            else ss++;
        }
        dfs1(root,0);
        if(n==2)cout<<"1\n";
        else cout<<dp[root][ss&1]<<"\n";
    }
}