hdu 4679 树状dp

思路：我们其实只需要枚举每条边，求得最小值就行了。

先dfs算出每个节点作为根时，其子树的最长路径，以及进过该节点的最长，次长，第三长路径。

然后在次dfs枚举求出切断某条边，求出这条边的两个端点为子树根，其子树的最长路径。b就是其中较大的。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<vector>

#define Maxn 200010

using namespace std;

int road[Maxn],Max[Maxn],lMax[Maxn],vi[Maxn],e,head[Maxn],dis[Maxn],ldis[Maxn],pr,ans,sMax[Maxn],lroad[Maxn];

struct Edge{

    int u,v,val,id,next;

}edge[Maxn*];

void init()

{

    memset(road,,sizeof(road));

    memset(Max,,sizeof(Max));

    memset(lMax,,sizeof(lMax));

    memset(vi,,sizeof(vi));

    memset(dis,,sizeof(dis));

    memset(ldis,,sizeof(ldis));

    memset(head,-,sizeof(head));

    memset(sMax,,sizeof(sMax));

    memset(lroad,,sizeof(lroad));

    e=;

}

void add(int u,int v,int val,int id)

{

    edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].id=id,edge[e].next=head[u],head[u]=e++;

    edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].id=id,edge[e].next=head[v],head[v]=e++;

}

void dfs(int u)

{

    int i,v;

    vi[u]=;

    for(i=head[u];i!=-;i=edge[i].next)

    {

        v=edge[i].v;

        if(vi[v]) continue;

        dfs(v);

        if(Max[v]+>Max[u])

        {

            sMax[u]=lMax[u];

            lroad[u]=road[u];

            lMax[u]=Max[u];

            Max[u]=Max[v]+;

            road[u]=v;

        }

        else

        if(Max[v]+>lMax[u])

        {

            sMax[u]=lMax[u];

            lMax[u]=Max[v]+;

            lroad[u]=v;

        }

        dis[u]=max(dis[u],Max[u]+lMax[u]);

        dis[u]=max(dis[u],dis[v]);

    }

}

void predfs(int u,int d,int pre,int fa)

{

    int i,v;

    vi[u]=;

    int now=;

    int a,b=;

    for(i=head[u];i!=-;i=edge[i].next)

    {

        v=edge[i].v;

        if(vi[v]) continue;

        a=edge[i].val;

        now=pre;

        if(road[u]==v)

        {

            now=max(d+lMax[u],now);

            now=max(lMax[u]+sMax[u],now);

            b=max(now,dis[v]);

            if(a*b<=pr)

            {

                if(a*b==pr)

                {

                    if(edge[i].id<ans)

                    ans=edge[i].id;

                }

                else

                pr=a*b,ans=edge[i].id;

            }

            predfs(v,max(d,lMax[u])+,now,u);

        }

        else

        if(lroad[u]==v)

        {

            now=max(d+Max[u],now);

            now=max(Max[u]+sMax[u],now);

            b=max(now,dis[v]);

            if(a*b<=pr)

            {

                if(a*b==pr)

                {

                    if(edge[i].id<ans)

                    ans=edge[i].id;

                }

                else

                pr=a*b,ans=edge[i].id;

            }

            predfs(v,max(d,Max[u])+,now,u);

        }

        else

        {

            now=max(d+Max[u],now);

            now=max(Max[u]+lMax[u],now);

            b=max(now,dis[v]);

            if(a*b<=pr)

            {

                if(a*b==pr)

                {

                    if(edge[i].id<ans)

                    ans=edge[i].id;

                }

                else

                pr=a*b,ans=edge[i].id;

            }

            predfs(v,max(d,Max[u])+,now,u);

        }

    }

}

int main()

{

    int n,i,j,m,t,u,v,w,Case=;

    scanf("%d",&t);

    while(t--)

    {

        init();

        scanf("%d",&n);

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

        {

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w,i);

        }

        int a,b;

        dfs();

        memset(vi,,sizeof(vi));

        pr=;

        ans=;

        predfs(,,,);

        printf("Case #%d: %d\n",++Case,ans);

    }

    return ;

}

巴特西

hdu 4679 树状dp

最新文章

热门文章