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:  [email protected] 
 *===========================================*/  
  
#include <iostream>   
#include <cstdio>   
#include <algorithm>   
#include <vector>   
#include <queue>   
#include <cmath>   
#include <cstring>   
#pragma comment(linker,"/STACK:102400000,102400000")   
using namespace std;  
#define MP make_pair   
typedef pair<int, int >PII;  
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<ans){  
        ans=temp;  
        ansid=pid;  
    }else if(temp==ans){  
        ansid=min(pid,ansid);  
    }  
    }  
    for(int e=head[u];e!=-1;e=E[e].next){  
        int v=E[e].v;  
        int w=E[e].w;  
        int id=E[e].id;  
        if(v==pre) continue;  
        dfs1(v,u,w,id);  
    }  
}  
  
int main(){  
    int T;  
    int n,cas=1;  
    scanf("%d",&T);  
    while(T--){  
        initEDGE();  
        scanf("%d",&n);  
        for(int i=1;i<n;i++){  
            int u,v,w;  
            scanf("%d%d%d",&u,&v,&w);  
            addEDGE(u,v,w,i);  
            addEDGE(v,u,w,i);  
        }  
        memset(depth,0,sizeof depth);  
        dfs(1,0);  
        memset(max1,0,sizeof max1);  
        memset(max2,0,sizeof max2);  
        memset(max3,0,sizeof max3);  
        ans=INF;  
        ansid=0;  
        dfs1(1,0,0,0);  
        printf("Case #%d: %d\n",cas++,ansid);  
    }  
    return 0;  
}  

/*==========================================

 *   @author: Dazdingo
 *   @blog:   blog.csdn.net/lfj200411
 *   @email:  [email protected]
 *===========================================*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
#define MP make_pair
typedef pair<int, int >PII;
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<ans){
        ans=temp;
        ansid=pid;
    }else if(temp==ans){
        ansid=min(pid,ansid);
    }
    }
    for(int e=head[u];e!=-1;e=E[e].next){
        int v=E[e].v;
        int w=E[e].w;
        int id=E[e].id;
        if(v==pre) continue;
        dfs1(v,u,w,id);
    }
}

int main(){
    int T;
    int n,cas=1;
    scanf("%d",&T);
    while(T--){
        initEDGE();
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addEDGE(u,v,w,i);
            addEDGE(v,u,w,i);
        }
        memset(depth,0,sizeof depth);
        dfs(1,0);
        memset(max1,0,sizeof max1);
        memset(max2,0,sizeof max2);
        memset(max3,0,sizeof max3);
        ans=INF;
        ansid=0;
        dfs1(1,0,0,0);
        printf("Case #%d: %d\n",cas++,ansid);
    }
    return 0;
}

#include <cstdio>   
#include <cctype>   
#include <vector>   
#include <algorithm>   
#include <cstring>   
#include <list>   
using namespace std;  
#pragma comment(linker, "/STACK:1024000000,1024000000")   
const int INF=0x3f3f3f3f;  
struct Edge{  
    int v,next;  
    int id;  
    int w;  
}E[100010*2];  
int head[100010],size;  
void addedge(int u,int v,int w,int id){  
    E[size].id=id;  
    E[size].v=v;  
    E[size].w=w;  
    E[size].next=head[u];  
    head[u]=size++;  
}  
void initedge(){  
    size = 0 ;  
    memset(head, -1,sizeof head);  
}  
int len,root;  
int p[100010];  
int q[100010];  
int man[100010];  
void dfs0(int u,int deep,int pre){  
    if(deep>len){  
        len=deep;  
        root=u;  
    }  
    for(int e=head[u] ; e!=-1 ; e=E[e].next){  
        int v=E[e].v;  
        if(v==pre) continue;  
        dfs0(v,deep+1,u);  
    }  
}  
int dep[100010];  
void dfs(int u,int pre){  
    q[u] = pre;  
    dep[u] = dep[pre] + 1;  
    for(int e=head[u] ; e!=-1 ; e=E[e].next){  
        int v=E[e].v;  
        if(v==pre) continue;  
        dfs(v,u);  
    }  
}  
int ans,ansid;  
void solve(int u,int pre){  
    for(int e=head[u] ; e!=-1 ; e=E[e].next){  
        int v=E[e].v;  
        int w=E[e].w;  
        int id=E[e].id;  
        if(v==pre) continue;  
        solve(v,u);  
        if(man[u]&&man[v]){  
            int a=man[u],b=man[v];  
            if(a>b) swap(a,b);  
            int tempmax=max((a-1) , (len+1-b) );  
            if(ans > w*tempmax){  
                ans=w*tempmax;  
                ansid=id;  
            }  
        }  
        else{  
            if(ans>w*len){  
                ans=w*len;  
                ansid=id;  
            }  
        }  
    }  
}  
int main(){  
    int n,T,cas=1;  
    scanf("%d",&T);  
    while(T--){  
        scanf("%d",&n);  
        initedge();  
        for(int i=1 ; i<n ; i++){  
            int u,v,w;  
            scanf("%d%d%d",&u,&v,&w);  
            addedge(u,v,w,i);  
            addedge(v,u,w,i);  
        }  
        len=-1;  
        dfs0(1,0,-1);  
        memset(p , 0 , sizeof p);  
        memset(man , 0 , sizeof man);  
        dfs(root,0);  
        int v=1,deep=1;  
        for(int i =1;i <= n;i++)  
            if(dep[v] < dep[i])  
                v = i;  
        int tmp=v;  
        len=dep[v]-1;  
        while(tmp){  
            man[tmp]=deep++;  
            tmp=q[tmp];  
        }  
        ans=INF;  
        solve(1,-1);  
        printf("Case #%d: %d\n",cas++,ansid);  
    }  
    return 0;  
}  

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#include <cstring>
#include <list>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const int INF=0x3f3f3f3f;
struct Edge{
    int v,next;
    int id;
    int w;
}E[100010*2];
int head[100010],size;
void addedge(int u,int v,int w,int id){
    E[size].id=id;
    E[size].v=v;
    E[size].w=w;
    E[size].next=head[u];
    head[u]=size++;
}
void initedge(){
    size = 0 ;
    memset(head, -1,sizeof head);
}
int len,root;
int p[100010];
int q[100010];
int man[100010];
void dfs0(int u,int deep,int pre){
    if(deep>len){
        len=deep;
        root=u;
    }
    for(int e=head[u] ; e!=-1 ; e=E[e].next){
        int v=E[e].v;
        if(v==pre) continue;
        dfs0(v,deep+1,u);
    }
}
int dep[100010];
void dfs(int u,int pre){
    q[u] = pre;
    dep[u] = dep[pre] + 1;
    for(int e=head[u] ; e!=-1 ; e=E[e].next){
        int v=E[e].v;
        if(v==pre) continue;
        dfs(v,u);
    }
}
int ans,ansid;
void solve(int u,int pre){
    for(int e=head[u] ; e!=-1 ; e=E[e].next){
        int v=E[e].v;
        int w=E[e].w;
        int id=E[e].id;
        if(v==pre) continue;
        solve(v,u);
        if(man[u]&&man[v]){
            int a=man[u],b=man[v];
            if(a>b) swap(a,b);
            int tempmax=max((a-1) , (len+1-b) );
            if(ans > w*tempmax){
                ans=w*tempmax;
                ansid=id;
            }
        }
        else{
            if(ans>w*len){
                ans=w*len;
                ansid=id;
            }
        }
    }
}
int main(){
    int n,T,cas=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        initedge();
        for(int i=1 ; i<n ; i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w,i);
            addedge(v,u,w,i);
        }
        len=-1;
        dfs0(1,0,-1);
        memset(p , 0 , sizeof p);
        memset(man , 0 , sizeof man);
        dfs(root,0);
        int v=1,deep=1;
        for(int i =1;i <= n;i++)
            if(dep[v] < dep[i])
                v = i;
        int tmp=v;
        len=dep[v]-1;
        while(tmp){
            man[tmp]=deep++;
            tmp=q[tmp];
        }
        ans=INF;
        solve(1,-1);
        printf("Case #%d: %d\n",cas++,ansid);
    }
    return 0;
}