能过样例,交上去全错。且错误都在第二行。
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N = 2e5 + 100;
int n;
int h[N], idx = 1;
int ver[N << 1], nxt[N << 1];
ll w[N << 1];
void add(int u, int v, ll c){
ver[++idx] = v;
nxt[idx] = h[u];
w[idx] = c;
h[u] = idx;
ver[++idx] = u;
nxt[idx] = h[v];
w[idx] = c;
h[v] = idx;
}
int a, b;
ll dis[N];
int fr[N], to[N];
bool ban[N];
void dfs(int u, int fa){
for(int i = h[u];i;i = nxt[i]){
int v = ver[i];
if(v == fa) continue;
dis[v] = dis[u] + w[i];
fr[v] = u;
dfs(v, u);
}
}
vector<int> d;
ll ex[N];
void dfs2(int u, int fa){
for(int i = h[u];i;i = nxt[i]){
int v = ver[i];
if(v == fa || ban[v]) continue;
dfs2(v, u);
ex[u] = max(ex[u], ex[v] + w[i]);
}
}
int main(){
scanf("%d",&n);
for(int i = 1, u, v;i < n;i++){
ll c;
scanf("%d%d%lld",&u,&v,&c);
add(u, v, c);
}
dfs(1, 1);
for(int i = 1;i <= n;i++) if(dis[i] >= dis[a]) a = i;
dis[a] = 0;fr[a] = -1;
dfs(a, a);
for(int i = 1;i <= n;i++) if(dis[i] >= dis[b] && i != a) b = i;
printf("%lld\n",dis[b]);
to[b] = -1;
for(int x = b;;x = fr[x]){
ban[x] = 1;
if(fr[x] != -1) to[fr[x]] = x;
else break;
}
// cout << a << " " << b << "\n";
// for(int i = 1;i <= n;i++) cout << fr[i] << " ";
// cout << "\n";
// for(int i = 1;i <= n;i++) cout << to[i] << " ";
// cout << "\n";
int l, r;
for(int i = a;i != -1;i = to[i]){
dfs2(i, i);
if(dis[b] - dis[i] <= ex[i]){r = i;break;}
}
for(int i = b;i != -1;i = fr[i]){
dfs2(i, i);
if(dis[i] <= ex[i]){l = i;break;}
}
printf("%d\n",r - l + 1);
return 0;
}