直径公共边

题目描述

小Q最近学习了一些图论知识。根据课本，有如下定义。

树:无回路且连通的无向图，每条边都有正整数的权值来表示其长度。如果一棵树有N个节点，可 以证明其有且仅有N-1 条边。

路径:一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b) 表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。

直径:一棵树上，最长的路径为树的直径。树的直径可能不是唯一的。

现在小Q想知道，对于给定的一棵树，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

---

输入

第一行包含一个整数N(1≤N≤200000)，表示节点数。

接下来N−1行，每行三个整数a,b,c，表示点a和点b之间有一条长度为c的无向边。

输出

共两行。第一行一个整数，表示直径的长度。第二行一个整数，表示被所有直径经过的边的数量。

输入样例1

6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100

输出样例1

1110
2

---

数据规模与限定

时间限制：1 s

内存限制：64 M

定义一条主直径，其它为次直径，直径的公共边上的点到达所以直径的端点距离相同

思路

• 思路都在注释了
• dfs求出一条直径
• 记录直径前驱和后继方向
• 保留直径上的点到左端点（或者右端点）的距离
• 再求一遍直径上面的点到达非直径上面的点的最大距离
• 最后处理得到直径公共边的左端点或者右端点
• 再遍历公共边，即可得到公共边数量

题解

#include <stdio.h>

using namespace std;

const int MAX_N = 2e5+5;

int n, ex, cnt;
long long ans;
int l, r; // 直径两个端点
//链式前向星 
int head[MAX_N], to[MAX_N << 1], nex[MAX_N << 1], v[MAX_N << 1], edge_cnt; 
int per[MAX_N], ne[MAX_N], vis[MAX_N];
long long dis[MAX_N], disa[MAX_N];

// 加边 
inline void add_edge(int a, int b, int c) {
    to[++edge_cnt] = b;
    v[edge_cnt] = c;
    nex[edge_cnt] = head[a];
    head[a] = edge_cnt;
    return ;
}
// 利用dfs可以省略vis数组，但是有个步骤需要用vis标记主直径上面的点
// s记录从根节点走到now的距离，f为now的父节点 
void dfs(const int& now, const long long& s, const int& f) { 
    
    if (s > ans) {
        ans = s;
        ex = now;
    }
    for (int i = head[now]; i; i = nex[i]) {
        if (f == to[i]) continue; //防止往上搜
        per[to[i]] = now; 
        dis[to[i]] = dis[now] + v[i];
        dfs(to[i], s + v[i], now);
    }
    return ;
}

void dfs1(const int& now, const long long& s) {
    vis[now] = 1;
    if (s > ans) {
        ans = s;
        ex = now;
    }
    for (int i = head[now]; i; i = nex[i]) {
        if (vis[to[i]]) continue; //防止往上搜
        per[to[i]] = now; 
        dis[to[i]] = dis[now] + v[i];
        dfs1(to[i], s + v[i]);
    }
    return ;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add_edge(a, b, c);
        add_edge(b, a, c);
    }
    per[1] = 0, dis[1] = 0;
    dfs(1, 0, 0); //寻找距离1最远的点 
    //printf("ans = %d, ee = %d\n", ans, ex);
    l = ex, ans = 0;
    per[l] = 0, dis[l] = 0;
    dfs(l, 0, 0); // 寻找距离l最远的点r 
    r = ex;
    //printf("ans = %d, ee = %d\n", ans, ex);
    //printf("主直径两端点：（%d，%d）\n", l, r);
    printf("%lld\n", dis[r]);
    
    //输出主直径上的点     
    int p = r;
    while (p) {
        vis[p] = 1; //标记主直径上的点 
        ne[per[p]] = p; //记录从主直径左端点l到右端点r的路径 
        disa[p] = dis[p]; //保留主直径上的点到达直径左端点l的距离 
        // 输出从主直径右端点r到左端点l路径上的点，和到达左端点l的距离 
        //printf("%d dis = %d\n", p, dis[p]);
        p = per[p]; 
    }
    //输出从主直径左端点到右端点的路径 
//    p = l;
//    while (p) {
        //printf("%d->", p);
//        p = ne[p];
//    } 
    //putchar('\n');
     
     
    //从左往右求出主直径上的点到其他非主直径点的最远距离 
    for (int i = l; i; i = ne[i]) {
        ex = i, ans = 0;
        dis[i] = 0;
        dfs1(i, 0);
        dis[i] = dis[ex]; // 主直径上的点到达非主直径点的最远距离 
        //printf("%d->%d = %d\n", i, ex, ans);
    }
    
//    p = l;
//    while (p) {
//        printf("p = %d, disa[p] = %lld, dis[p] = %lld\n", p, disa[p], dis[p]);
//        p = ne[p];        
//    }
    
    //从右往左找到所有直径共同经过的边的第一个点 
    p = r;
    while (p && disa[p] != dis[p]) {
        //printf("p = %d, disa[p] = %lld, dis[p] = %lld\n", p, disa[p], dis[p]);
        p = per[p];
    }
    
    while (p && (disa[p] + dis[p] != disa[r])) {
        //printf("p = %d, disa[p] = %lld, dis[p] = %lld\n", p, disa[p], dis[p]);
        p = ne[p], ++cnt;
    }
    printf("%d\n", cnt);
    return 0;
}