大佬求助！！！

常规
1

2. 树的直径

题目ID：7169必做题100分

最新提交：

Wrong Answer

0 分

历史最高：

Wrong Answer

0 分

时间限制: 1000ms

空间限制: 512000kB

题目描述

题目描述

求一棵树的直径

换句话说就是找出一条链,使得链的两端点长度最长

输入格式

第一行一个数n

接下来n-1行，每行三个数x,y,z,表示x到y有一条长度为z的边

样例输入

7 1 6 13 6 3 9 3 5 7 4 1 3 2 4 20 4 7 2

样例输出

52

数据范围

𝑛≤10000，𝑧≤1000n≤10000，z≤1000

时空限制

1𝑠，512𝑀1s，512M

样例没过：

#include<iostream>
#include<limits>
#include<vector>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+10;
vector<int> head(MAX_N,-1);
typedef struct node{
    int to,nxt,high;
    node():to(-1),nxt(-1){}
}node;
node eg[2*MAX_N];
int n,ans=0,cnt=0,dp[MAX_N];
bool it[MAX_N];
void add(int u,int v,int w){
    eg[cnt].to=v;
    eg[cnt].high=w;
    eg[cnt].nxt=head[u];
    head[u]=cnt;
    cnt++;
    return;
}
void solve(int u){
    it[u]=true;
    for(int i=head[u],x,y;~i;i=eg[i].nxt){
        x=eg[i].to,y=eg[i].high;
        if(it[x])continue;
        solve(x);
        ans=max(ans,dp[u]+dp[x]+y);
        dp[u]=max(dp[u],dp[x]+dp[y]);
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1,a,b,c;i<n;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    solve(1);
    cout<<ans;
    return 0;
}
2 个赞
2

稍等 :rose:

2 个赞
3

要2次dfs，先找到一端点，再找直径

1 个赞
4

给你dfs模板

1 个赞
5 
void dfs(int u,int father,int w){
	dep[u]=dep[father]+w;//权值累加
	for(auto p:g[u])//找到达点（这是pair类型的）
		if(p.v!=father) dfs(p.v,u,p.w);//递归
	if(dep[u]>dep[q]) q=u;//如果权值更大，说明越接近端点，所以更新
}

这样一次dfs求出的q就是直径的一端，然后再来一次即可

1 个赞
6

这个y是边权吧，为什么要dp[y]

2 个赞
7

@向耕立 @向耕立

8

我就要用树形dp

1 个赞