求调!!!!!
查看原帖
求调!!!!!
819682
Exile_Code楼主2024/3/22 19:12
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <math.h>
#include <functional>



#define ll              unsigned long long 
#define pii             pair<ll ,ll>
#define cy              cout<<"YES"<<endl
#define cn              cout<<"NO"<<endl
#define forn(i,begin,end,add)	for(ll (i)=(begin);(i)<=(end);(i)+=(add))	//begin是i的起始,end是i的终止,add是每次加的大小
#define rforn(i,begin,end,sub)  for(ll (i)=(end);(i)>=(begin);(i)-=(sub))	//r是倒序遍历
#define vv              vector
#define inf32           INT32_MAX/2
#define inf64           INT64_MAX/2
#define LD              double
#define PI              acos(-1)
#define debug(a,b)		cout<<a<<b
#define eps				1e-12


const int N = 4e5 + 100;
const int mod = 998244353;
ll T;

int n;
vv<vv<pii>>tree;
vv<ll>d1;
vv<ll>d2;
vv<ll>w;
int bfs(int x,vv<ll>&d) {
    vv<int>flag(n+2);
    queue<int>q;
    q.push(x);
    while (q.size()) {
        int floor = q.size();
        while (floor--) {
            int nd = q.front();     flag[nd] = 1;   q.pop();
            for(auto a:tree[nd]) {
                if (!flag[a.first])
                    q.push(a.first), d[a.first] = d[nd] + a.second;
            }
        }
    }
    ll mx = 0;

    forn(i, 1, n, 1) {
        if (d[i] > d[mx])
            mx = i;
    }
    return mx;
}


vv<vv<int>>fa;//存u点向上跳2的i次方层的祖先结点
vv<vv<int>>e;
vv<int>dep;//存深度

//倍增法求公共祖先,时间复杂度(n+m)*logn
void init(int n) {
    fa = vv<vv<int>>(n + 1, vv<int>(30));
    e = vv<vv<int>>(n + 1);
    dep = vv<int>(n + 1);
    dep[0] = -1;
}
void dfs(int u, int father) {
    dep[u] = dep[father] + 1;
    fa[u][0] = father;
    for (int i = 1; i <= 19; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];//实际上是一半一半的跳
    }
    for (int v : e[u])
        if (v != father)	
            dfs(v, u);

}
int lca(int u, int v) {
    if (dep[u] < dep[v])swap(u, v);

    for (int i = 19; i >= 0; i--)
        if (dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    if (u == v)return v;//在同一条链上

    for (int i = 19; i >= 0; i--)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];//最后跳到了公共祖先的下一层	
    return fa[u][0];
}
void solve() {


    cin >> n;
    init(n);
    tree.resize(n + 1);  d1.resize(n + 1);d2.resize(n + 1);
    forn(i, 1, n - 1, 1) {
        int a, b; cin >> a >> b;
        int c; cin >> c;
        e[a].push_back(b);
        e[b].push_back(a);
        tree[b].push_back({ a,c });
        tree[a].push_back({ b,c });
    }
            
    vv<ll>d3(n + 1);
    int nd = bfs(1, d1);
    int mx = bfs(nd, d2);
    bfs(mx, d3);

    //找两条直径的四个端点
    int mx1 = -1, mx2 = -1;
    int nd1 = -1 , nd2 = -1;
    
    forn(i, 1, n, 1) {
        if (d2[i] == d2[mx]) {
            if (mx1 == -1){
                mx1 = i; continue;
            }
            if (mx1 && nd2 == -1) {
                mx2 = i;  break;
            }
        }
    }
    forn(i, 1, n, 1){
        if (d3[i] == d2[mx]){
            if (nd1 == -1)  {
                nd1 = i;   continue;
            }
            if (nd1 && nd2 == -1){
                nd2 = i;    break;
            }
        }
    }


    dfs(nd1, 0);
    
    ll ans = 0;
    cout << d3[nd] << endl;
    if (nd2 == -1) {
        if (mx2 == -1)
            cout << dep[mx1] << endl;
        else
            cout << dep[lca(mx1,mx2)] << endl;

    }
    else {
        if (mx2 == -1)
            cout << dep[lca(mx2, nd2)] - dep[mx1] << endl;
        else
            cout << dep[lca(mx2, mx1)] - dep[lca(mx1, nd2)] << endl;
    }


}
int main() {

    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    T = 1;
   // cin >> T;
    while (T--)
        solve();
    return 0;

}


2024/3/22 19:12
加载中...