简单打卡

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

// acwing 389 直径
/*
主要是求解一颗树中的多条直径所经过的最多的公共边
首先由直径的性质,两次dfs寻找距离当前最远的点找到一条直径
将该条路径抽出变成一条直线,并删除(vis),通过夹逼法求解处两边端点分别
可以到达的最远距离依旧使用dfs,之后进行比较,如果是相等,lr便可向中心移动
*/ 
const int N = 2e5 + 10,M = 2 * N;
int h[N],e[M],ne[M],w[M],idx;
int father[N],vis[N];
ll dist[N];
vector<ll> v,td,val;
int n;

void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

// 返回到当前节点深度最深的点
int dfs(int u,int fa)
{
    int maxpos = u;
    for(int i = h[u]; ~i ;i = ne[i])
    {
        int j = e[i];
        if(vis[j] || j == fa) continue;
        father[j] = u;
        dist[j] = dist[u] + w[i];
        int t = dfs(j,u);
        if(dist[t] > dist[maxpos]) maxpos = t;
    }
    return maxpos;
}

int main()
{
    freopen("/Users/dy/Desktop/sol.in","r",stdin);
    memset(h,-1,sizeof h);
    memset(vis,0,sizeof vis);
    memset(dist,0,sizeof dist);
    memset(father,0,sizeof 0);
    cin >> n;
    for(int i = 1;i < n;i ++)
    {
        int a,b,c; cin >> a >> b >> c;
        add(a,b,c),add(b,a,c);
    }
    int up = dfs(1,-1);
    dist[up] = 0; father[up] = 0;
    int down = dfs(up,-1);
    cout << dist[down] << endl;
    // up -> down是一条链
    for(int i = down; i;i = father[i]) v.push_back(i);
    reverse(v.begin(),v.end());
    for(auto t : v) vis[t] = true,td.push_back(dist[t]);

    int l = 0,r = v.size() - 1;
    // 每次取出一个点进行遍历
    for(auto t : v)
    {
        dist[t] = 0;
        ll len = dist[dfs(t,-1)];
        val.push_back(len);
    }

    // move l
    for(int i = 0;i < v.size();i ++)
        if(val[i] == td[i]) l = i;
    // move r
    for(int i = v.size() - 1;i >= 0;i --)
        if(td[td.size() - 1] - td[i] == val[i])
            r = i;
    // assert(l < r);
    cout << r - l << endl;
    return 0;
}