Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 树形DP,两次DFS,求树的直径

Posted by 2742195759 at 2016-03-27 11:41:36 on Problem 1985
```#include <stdio.h>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define inf 0x3f3f3f3f
#define mem0(x , y)  memset(x , y , sizeof(x))
#define ll long long
using namespace std;
struct node{
int s, e , w ,next ;
} ;
node Edge[100000] ;
int head[50000] , cnt = 0 ;
Edge[cnt].s = s ; Edge[cnt].e = e ; Edge[cnt].w = w ; Edge[cnt].next = head[s] ;
}
int dis[100000][3] ;
void dfs(int s , int pre) {
int f = 0 ;
int mx = 0 , ms = -1 , mi = -1 ;
for(int i=head[s] ; i!=-1 ; i=Edge[i].next){
int v = Edge[i].e ;
if(pre == v) continue ;
f ++ ;
dfs(v, s) ;
if(mx <= dis[v][0] + Edge[i].w) {
ms = mx ; mx = dis[v][0] + Edge[i].w ; mi = v ;
}
}
dis[s][0] = mx ; dis[s][1] = ms ; dis[s][2] = mi ;
///printf("dfs %d -> %d\n" , s, dis[s][0]) ;
}
int ans = 0 ;
void dfs2(int s,int pre){
///printf("%d -> %d\n" , s, dis[s][0]) ;
ans = max(ans , dis[s][0]) ;
for(int i=head[s] ; i!=-1 ; i=Edge[i].next){
int v = Edge[i].e ;
if(pre == v) continue ;
if(dis[s][2] == v){
if(dis[s][0] - Edge[i].w <= Edge[i].w + dis[s][1]){
dis[v][0] = Edge[i].w + dis[s][1] ;
dis[v][2] = s ;
}
}
else {
dis[v][0] = Edge[i].w + dis[s][0] ;
dis[v][2] = s ;
}
dfs2(v , s) ;
}
}
int main(){
///freopen("1" , "r" ,stdin) ;
int n , m ;
scanf("%d%d",&n,&m) ;
int ta , tb ,tc ;
char td[4];
for(int i=0;i<m;i++){
scanf("%d%d%d%s",&ta,&tb,&tc,td) ;
add(ta , tb ,tc ) ;
add(tb , ta ,tc ) ;
}
dfs(1 , -1) ;
dfs2(1 , -1) ;
printf("%d\n",ans) ;
}
```

Followed by: