这道题用了3中思路写，一种wa，一种tle，只用用bfs写的过了，而且用bfs写的测试了一下数据，发现数据应该始终是在包含节点1的树中得到的～～，很难以理解前两种做法的wa

下面是wa的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 40005;
int f[maxn], g[maxn], longest[maxn];
vector<int> son[maxn], w[maxn];
bool vis[maxn];
int dfs(int root){
    int i, j;
    int est = 0, esti=-1, er=0;
    if(f[root]!=-1) return f[root];
    if(son[root].empty()) return f[root] = 0;
    for(i=0;i<son[root].size();i++){
        if(dfs(son[root][i])+w[root][i]>est){
            est = f[son[root][i]]+w[root][i];
            esti = i;
        }
    }
    longest[root] = esti;
    for(i=0;i<son[root].size();i++){
        if(f[son[root][i]]+w[root][i]>er&&i!=longest[root]){
            er = f[son[root][i]]+w[root][i];
        }
    }
    g[root] = er;
    return f[root] = est;
}

void Init(int n){
    int i;
    for(i=0;i<=n;i++){
        f[i] = g[i] = longest[i] = -1;
        son[i].clear();
        w[i].clear();
        vis[i] = 0;
    }
}
int main(){
    int i, j, k, n, m, ans;
    int x1, x2, l;
    char opt;
    while(~scanf("%d%d",&n,&m)){
        Init(n);
        for(i=0;i<m;i++){
            scanf("%d%d%d",&x1,&x2,&l);
            scanf(" %c",&opt);
            if(opt=='E'||opt=='S'){
                son[x1].push_back(x2);
                w[x1].push_back(l);
                vis[x2] = 1;
            }
            else{
                son[x2].push_back(x1);
                w[x2].push_back(l);
                vis[x1] = 1;
            }
        }
        for(i=1;i<=n;i++){
            if(vis[i]==0&&f[i]==-1){
                f[i] = dfs(i);
            }
        }
        ans = 0;
        for(i=1;i<=n;i++){
            ans = max(ans,f[i]+g[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}