HDU2196 树状DP - c++编程基础

树形DP题，做的有些艰难，以前没怎么做过这方面的题目，有些理不清楚，题意很简单，就是给你一些电脑，每两台电脑之间若要连通是需要一定的权值的，把这些电脑按照input连在一起，形成一颗树，问树中每一个节点到另一个节点（不确定是哪个几点）的距离值中最大距离，

我们知道每一个节点最大值无非来自两个地方，1：来自于他的子树中2；从他父亲节点过来的，但是有个地方要注意，从父节点过来的有可能是直接的，也有可能是父亲的最大距离加上他与父亲的距离，意思就是次长距离加上他与父亲的距离，所以需要两边DFS，第一次从他子树中寻找出最大距离跟次大距离，然后第二次DFS直接对父亲过来的进行更新即可

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // const int N = 10000 + 5; int n; int cnt; int head[N];//头节点 int maxn[N];//该节点下面子树最大距离 int smaxn[N];//该节点下面子树次大距离 int maxid[N];//最大距离所对应的ID int smaxid[N];//次大距离所对应的ID struct Node { int to; int nex; int w; }edge[N*2]; void clear() { cnt= 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { edge[cnt].to=v; edge[cnt].w=w; edge[cnt].nex=head[u]; head[u]=cnt++; } //求节点V子树的最大距离，p是v的父亲节点 void dfs1(int u,int p) { maxn[u] = 0; smaxn[u] = 0; for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(v == p)continue; dfs1(v,u); if(smaxn[u] < maxn[v] + edge[i].w) { smaxn[u] = maxn[v] + edge[i].w; smaxid[u] = v; if(smaxn[u] > maxn[u]) { swap(smaxn[u],maxn[u]); swap(smaxid[u],maxid[u]); } } } } //p是u的父亲节点， void dfs2(int u,int p) { for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].to; if(v == p)continue; if(v == maxid[u]) { if(edge[i].w + smaxn[u] > smaxn[v]) { smaxn[v] = edge[i].w + smaxn[u]; smaxid[v] = u; if(smaxn[v] > maxn[v]) { swap(smaxn[v],maxn[v]); swap(smaxid[v],maxid[v]); } } } else { if(edge[i].w + maxn[u] > smaxn[v]) { smaxn[v] = edge[i].w + maxn[u]; smaxid[v] = u; if(smaxn[v] > maxn[v]) { swap(smaxn[v],maxn[v]); swap(maxid[v],smaxid[v]); } } } dfs2(v,u); } } int main() { while(scanf("%d",&n)==1) { clear(); int v,w; for(int i=2;i<=n;i++) { scanf("%d %d",&v,&w); addedge(i,v,w); addedge(v,i,w); } dfs1(1,-1); dfs2(1,-1); for(int i=1;i<=n;i++) printf("%d\n",maxn[i]); } return EXIT_SUCCESS; }