BZOJ4871 Shoi2017摧毁“树状图”（树形dp）

　　设f[i][0/1/2/3/4/5]表示i子树中选一条链不包含根/i子树中选一条链包含根但不能继续向上延伸/i子树中选一条链可以继续向上延伸/选两条链不包含根/选两条链包含根但不能继续向上延伸/选两条链能继续向上延伸，大力讨论即可。代码看起来很(mo)有(ming)意(qi)思(miao)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 500010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T,n,p[N],f[N][],t;

int mx[][];

struct data{int to,nxt;

}edge[N<<];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

inline void up(int &x,int y){x=max(x,y);}

inline int max(int x,int y,int z){return max(max(x,y),z);}

void update(int x)

{

    for (int i=;i<;i++)

        for (int j=;j<;j++)

        if (f[x][i]>f[mx[j][i]][i])

        {

            for (int k=;k>j;k--) mx[k][i]=mx[k-][i];

            mx[j][i]=x;break;

        }

}

int findmx(int x){return f[mx[][x]][x];}

int findmx(int x,int y)

{

    if (mx[][x]!=mx[][y]) return f[mx[][x]][x]+f[mx[][y]][y];

    return max(f[mx[][x]][x]+f[mx[][y]][y],f[mx[][x]][x]+f[mx[][y]][y]);

}

int findmx(int x,int y,int z)

{

    int s=-n;

    for (int i=;i<;i++)

        for (int j=i+;j<;j++)

            for (int k=;k<;k++)

            if (mx[k][z]!=mx[i][x]&&mx[k][z]!=mx[j][y]) up(s,f[mx[k][z]][z]+f[mx[i][x]][x]+f[mx[j][y]][y]);

    return s;

}

int findmx(int a,int b,int c,int d){return f[mx[][a]][a]+f[mx[][b]][b]+f[mx[][c]][c]+f[mx[][d]][d];}

void dfs(int k,int from)

{

    int son=;

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from) son++,dfs(edge[i].to,k);

    memset(mx,,sizeof(mx));

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from) update(edge[i].to);

    f[k][]=max(findmx(),findmx()+,findmx()+);

    f[k][]=findmx(,)+son-;

    f[k][]=max(son,findmx()+son-);

    f[k][]=max(findmx(),findmx()+,findmx()+);

    for (int i=;i<;i++)

        for (int j=i;j<;j++)

        up(f[k][],findmx(i,j)+-(i==)-(j==));

    f[k][]=max(findmx(,,,)-,max(findmx(,,)-,findmx(,,)-),findmx(,)-)+son;

    f[k][]=max(max(findmx()-,findmx(,,)-,max(findmx(,),findmx(,),findmx(,))-),max(findmx(),findmx(),findmx())-)+son;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4871.in","r",stdin);

    freopen("bzoj4871.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();int op=read();

    while (T--)

    {

        n=read();if (op>=) read(),read();if (op==) read(),read();

        t=;for (int i=;i<=n;i++) p[i]=;

        f[][]=f[][]=f[][]=f[][]=f[][]=f[][]=-n;

        for (int i=;i<n;i++)

        {

            int x=read(),y=read();

            addedge(x,y),addedge(y,x);

        }

        dfs(,);

        printf("%d\n",max(max(f[][],f[][],f[][]),max(f[][],f[][],f[][])));

    }

    return ;

}