题解 | #马拉松#

I.马拉松

时间复杂度：

题意

    有一棵树，如果先经过点再经过点就会遇到警察拦截，统计有多少简单路径是依次经过这两点的？

数据范围

分析

    单独考虑中的一点，不难发现，当作为根时，所有不属于的路径上的子节点都是满足条件的，同理；所以根据乘法原理可知，最终答案就是，表示i节点（包含自身）的不经过路径的子树大小.
    问题转化为求的特定子树大小，我们只需要找到在这条路径上的的父节点，再在遍历的时候加以约束即可（详见代码解释）；一开始分别对和作为起点DFS,当作为起点能找到子节点,那么此时的节点一定是的父节点，作为起点也同理，这是因为树的两点之间的路径是唯一的.
    最后，通过两次限定父节点的DFS即可计算出特定的与，最后乘积记得开long long ~

Code:

#include <bits/stdc++.h>
#define endl '\n'
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x, y;cin >> n >> x >> y;
    vector<vector<int>> e(n + 1);
    for (int i = 1; i < n; i++){
        int u, v;cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    int cnt, cnt1, cnt2;
    int goal, fa_x, fa_y; //x的父节点，y的父节点
    auto dfs = [&](auto dfs, int u, int fa,int g) -> void{
        for (auto s : e[u]){
            if (s == fa)continue;
            if(s==g){ //说明找到了另一端点，则当前的u就是要找的fa_x或fa_y
                goal = u;
                return;
            }
            dfs(dfs, s, u, g);
        }
    };
    auto calc = [&](auto calc, int u, int fa) -> void {
        for(auto s:e[u]){
            if(s==fa)continue;
            cnt++;
            calc(calc, s, u);
        }
    };
    dfs(dfs, x, 0, y); //x开始找fa_y
    fa_y = goal; 
    dfs(dfs, y, 0, x); //y开始找fa_x
    fa_x = goal;
    cnt = 1;
    calc(calc, x, fa_x); //通过限定x在路径上的父节点，来阻止该条路径的遍历
    cnt1 = cnt;
    cnt = 1;
    calc(calc, y, fa_y);
    cnt2 = cnt;
    i64 ans = cnt1 * cnt2;
    //cout << cnt1 << ' ' << cnt2 << endl;
    cout << ans << endl;
    return 0;
}