hdu 4679 Terrorist’s destroy (一)

题目大意：

有个生成树，每条边长度是1

恐怖分子炸掉其中的一条边后分为两棵树

得到值为temp两棵树的直径中较大的直径乘以这条边的权值

求炸掉哪一条边得到的temp最小

解法1：

树形DP，求每个节点的所有分支的最大值 次大值 第三大值

砍掉一条边后，在三个值中选择两个未被砍的值就是这棵树的直径

解法2：

两次求整棵树的直径

如果砍掉的边不在直径上，那么temp=w*直径

如果砍掉了直径上的边。那么temp=w*max((a-1),(len+1-b)

其中len是直径

/*========================================== 
 
 *   @author: Dazdingo 
 *   @blog:   blog.csdn.net/lfj200411 
 *   @email:  lfj200411@163.com 
 *===========================================*/  
  
#include    
#include    
#include    
#include    
#include    
#include    
#include    
#pragma comment(linker,"/STACK:102400000,102400000")   
using namespace std;  
#define MP make_pair   
typedef pairPII;  
const int INF = 0x3f3f3f3f;  
const double PI  = acos(-1.0);  
struct EDGE{  
    int next,w,v,id;  
}E[100010*2];  
int head[100010];  
int size;  
void initEDGE(){  
    size=0;  
    memset(head,-1,sizeof head);  
}  
void addEDGE(int u,int v,int w,int id){  
    E[size].v=v;  
    E[size].id=id;  
    E[size].w=w;  
    E[size].next=head[u];  
    head[u]=size++;  
}  
int ans,ansid;  
int depth[100010];  
int max1[100010],max2[100010],max3[100010];  
int v1[100010],v2[100010],v3[100010];  
int dfs(int u,int pre){  
    for(int e=head[u];e!=-1;e=E[e].next){  
        int v=E[e].v;  
        if(pre==v) continue;  
        depth[u]=max(depth[u],dfs(v,u)+1);  
    }  
    return depth[u];  
}  
void dfs1(int u,int pre,int prew,int pid){  
    int temp;  
    for(int e=head[u];e!=-1;e=E[e].next){  
        int v=E[e].v;  
        if(v==pre) continue;  
        temp=depth[v]+1;  
        if(temp>max1[u]){  
            max3[u]=max2[u];v3[u]=v2[u];  
            max2[u]=max1[u];v2[u]=v1[u];  
            max1[u]=temp;  
            v1[u]=v;  
        }else if(temp>max2[u]){  
            max3[u]=max2[u];v3[u]=v2[u];  
            max2[u]=temp;  
            v2[u]=v;  
        }else if(temp>max3[u]){  
            max3[u]=temp;  
            v3[u]=v;  
        }  
    }  
    temp=0;  
    if(pre){  
        if(v1[pre]!=u) temp=max1[pre]+1;  
        else if(v2[pre]!=u) temp=max2[pre]+1;  
        else temp=max3[pre]+1;  
    if(temp>max1[u]){  
        max3[u]=max2[u];v3[u]=v2[u];  
        max2[u]=max1[u];v2[u]=v1[u];  
        max1[u]=temp;  
        v1[u]=pre;  
    }else if(temp>max2[u]){  
        max3[u]=max2[u];v3[u]=v2[u];  
        max2[u]=temp;  
        v2[u]=pre;  
    }else if(temp>max3[u]){  
        max3[u]=temp;  
        v3[u]=pre;  
    }  
    int umax1=max1[u];  
    int umax2=max2[u];  
    int premax1=max1[pre];  
    int premax2=max2[pre];  
    if(v1[u]==pre) umax1=max3[u];  
    else if(v2[u]==pre) umax2=max3[u];  
    if(v1[pre]==u) premax1=max3[pre];  
    else if(v2[pre]==u) premax2=max3[pre];  
    temp=max(umax1+umax2,premax1+premax2)*prew;  
    if(temp
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define MP make_pair
typedef pairPII;
const int INF = 0x3f3f3f3f;
const double PI  = acos(-1.0);
struct EDGE{
    int next,w,v,id;
}E[100010*2];
int head[100010];
int size;
void initEDGE(){
    size=0;
    memset(head,-1,sizeof head);
}
void addEDGE(int u,int v,int w,int id){
    E[size].v=v;
    E[size].id=id;
    E[size].w=w;
    E[size].next=head[u];
    head[u]=size++;
}
int ans,ansid;
int depth[100010];
int max1[100010],max2[100010],max3[100010];
int v1[100010],v2[100010],v3[100010];
int dfs(int u,int pre){
    for(int e=head[u];e!=-1;e=E[e].next){
        int v=E[e].v;
        if(pre==v) continue;
        depth[u]=max(depth[u],dfs(v,u)+1);
    }
    return depth[u];
}
void dfs1(int u,int pre,int prew,int pid){
    int temp;
    for(int e=head[u];e!=-1;