[NOI 2003 day2 逃学的小孩]树形dp

【提交地址】http://acm.nankai.edu.cn/p1092.html

【题目大意】给出一棵树，让你求树上任意三点A、B、C，在满足|AB|<=|BC|的情况，最大的|AB|+|BC|。

【算法分析】

就是树形dp，F[I,0]表示从儿子那来的最长的路径，F[I,1]表示从儿子那来的第二长的路径。然后D[I]表示从儿子那来的第3的路径or从父亲那来的最长路径。

然后转移就很简单了。

【其它】WA了超多遍，一开始是没想到可以从父亲那里来，后来是没想到可以从第3个枝那里来。

用了那么多memset和STL的东西，居然我是第一。。。

【CODE】

#include #include #include using namespace std;
const long long N=211111;
struct gtp{long long y,w,next;}g[600000];
long long n,m,e,ls[N],v[N];
long long f[N][3],d[N],ans=0,list[3];

void add(long long x,long long y,long long w){
    e++;
    g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}   

void init(){
    e=0;
    memset(ls,0,sizeof(ls));
    memset(f,0,sizeof(f));
    memset(d,0,sizeof(d));
    scanf("%lld %lld",&n,&m);
    for (long long i=1;i<=m;i++){
        long long x,y,w;
        scanf("%lld %lld %lld",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }   
}   

void dfs(long long k){
    v[k]=1;
    for (long long t=ls[k];t;t=g[t].next)
      if (!v[g[t].y]){
          dfs(g[t].y);
         long long x=f[g[t].y][0]+g[t].w;
          if (x>f[k][0]){
              f[k][2]=f[k][1];
              f[k][1]=f[k][0];
              f[k][0]=x;
          }   
          else
          if (x>f[k][1]){
              f[k][2]=f[k][1];
              f[k][1]=x;
          }   
          else if (x>f[k][2]) f[k][2]=x;
      }
}   

void dfs2(long long k){
    v[k]=1;
    for (long long t=ls[k];t;t=g[t].next)
      if (!v[g[t].y]){
         long long tmp;
          if (f[g[t].y][0]+g[t].w==f[k][0]) tmp=f[k][1];
                                       else tmp=f[k][0];
          tmp=max(tmp,d[k])+g[t].w;
          d[g[t].y]=tmp;
          dfs2(g[t].y);
      }   
    d[k]=max(d[k],f[k][2]);
    list[0]=d[k]; list[1]=f[k][0]; list[2]=f[k][1];
    if (list[0]>list[1]) swap(list[0],list[1]);
    if (list[0]>list[2]) swap(list[0],list[2]);
    if (list[1]>list[2]) swap(list[1],list[2]);
    ans=max(ans,list[0]+2*list[1]+list[2]);
}   

int main(){
    init();
    dfs(1);
    memset(v,0,sizeof(v));
    dfs2(1);
    printf("%lldn",ans);
}