【Luogu】P3174毛毛虫（树形DP）

　　树形DP水题，设f[x][0]是以x为根的子树，内部只有半条链（就是链的两个端点一个在子树里，一个不在子树里）的最大值，f[x][1]是以x为根的子树，内部有一条完整的链（选两个内部的子树作为链的左端点和右端点）的最大值。

　　于是可以很轻松的得出DP方程：

　　一开始f[x][0]=f[x][1]=1

　　然后dfs，深搜x的子树，记录一下x有多少子节点的同时记录子树的最大半链和次大半链（用来在转移的时候凑成x子树内的整个链）。最后注意细节乱搞搞就行了。

　　本题不考思维但是比较考验考虑细节的能力。

　　（具体有哪些坑点不知道，因为是1A）

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#define maxn 300010

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int f[maxn][];

struct Edge{

    int next,to;

}edge[maxn*];

int head[maxn],num;

inline void add(int from,int to){

    edge[++num]=(Edge){head[from],to};

    head[from]=num;

}

void dfs(int x,int fa){

    int fir=,sec=,son=;

    f[x][]=f[x][]=;

    for(int i=head[x];i;i=edge[i].next){

        int to=edge[i].to;

        if(to==fa)    continue;

        son++;

        dfs(to,x);

        if(fir<f[to][]){

            sec=fir;fir=f[to][];

        }

        else if(sec<f[to][])    sec=f[to][];

    }

    if(son>)    f[x][]=max(f[x][],fir+sec+son-);

    else         f[x][]=max(f[x][],fir+);

    f[x][]=max(f[x][],fir+son);

}

int main(){

    int n=read(),m=read();

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

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

        add(x,y);

        add(y,x);

    }

    dfs(,);

    int ans=f[][];

    for(int i=;i<=n;++i)    ans=max(ans,f[i][]+);

    printf("%d\n",ans);

    return ;

}

巴特西

【Luogu】P3174毛毛虫（树形DP）

最新文章

热门文章