Gym 101002I Tourists LCA板子题

题目链接：https://codeforces.com/gym/101002/attachments i题
题意：n2e5. 给你n个点，n-1条边建立一个无向图或者是树，边的权值都为1。现在让你求从1到n每个点u到一个点v的距离累加和。u与v满足：1. u|v的关系 2.v在1-n之间。
样例：

思路：
u,v一共nlogn组，暴力枚举这些点。剩下的关键如何求他们间的距离。我们以任意一个点为根节点建立一颗树，标记每个点的深度，随后对一组u,v找他们lca（最近的公共父亲结点），以这个点为参考坐标，两两深度相减，最后累加。其中找lca，我用的是倍增法+log数组优化常数，复杂度logn。所以这道题最终复杂度是nlognlogn。
其实可以一句话概括，lca板子题。可以去搜博客和b站学习，我是b站学的。
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 2e5+5;
int depth[maxn];
int father[maxn][20];
vector<int>e[maxn];
int lg[maxn];
void dfs(int nowp,int fa){
    depth[nowp] = depth[fa]+1;
    father[nowp][0] = fa;
    for1(i,lg[depth[nowp]]+1) father[nowp][i] = father[father[nowp][i-1]][i-1];
    for(auto x:e[nowp])if(x!=fa)dfs(x,nowp);
}

int lca(int u,int v){
    if(depth[u]<depth[v]) swap(u,v);
    while(depth[u]!=depth[v]){
        u = father[u][lg[depth[u]-depth[v]]];
    }
    if(u==v) return u;
    for(int j = lg[depth[u]];j>=0;j--){
        if(father[u][j]!=father[v][j]){
            u = father[u][j];
            v = father[v][j];
        }
    }
    return father[u][0];
}

int main(){
    IO;
    lg[0] = -1;
    for1(i,maxn-1) lg[i] = lg[i>>1]+1;
    int n;cin>>n;
    forn(i,n-1){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0);
    ll ans = 0;
    for1(i,n){
        for(int j = i+i;j<=n;j+=i){
            int x = lca(i,j);
            ans += abs(depth[x]-depth[i])+abs(depth[x]-depth[j])+1;
        }
    }
    cout << ans<<'
';
    return 0;
}