2020 wannafly camp day1 E 树与路径 —— 树上差分

题目链接：点我啊╭(╯^╰)╮

题目大意：

    有根树，求若干路径的权值和
    对一条路径的权值定义为：
    从起点到终点的最短路径中，向上走的边数 $\times$ 向下走的边数
    求根节点为 $1?n$时的答案

解题思路：

    对于一条路径 $(u,v)$，设长度为 $len$，$lca$ 到 $u$ 的距离为 $x$
    $an{s}_{lca}=x?(len?x)$，设 $lca$ 沿 $u$ 方向的儿子为 $son$
    $an{s}_{son}=(x?1)?(len?x+1)$
    $an{s}_{lca}?an{s}_{son}=len?2x+1$

    对于 $len+1$ 这部分，等同于这条路径上的所有点权 $+=len+1$
    对于 $?2x$ 这部分，也可以用差分处理：
    点 $u$ 的 $x$ 为 $1$，其父亲为 $2$，依次是 $3...$
    也就是差分处理等差数列的思想

核心：树上差分处理等差数列

#include<bits/stdc++.h>
#define rint register int
#define x first
#define y second
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,ll>;
const int maxn = 3e5 + 5;
int n, m, f[maxn][35];
ll ans[maxn], dep[maxn];
vector <int> g[maxn];
pii a[maxn];void dfs1(int u, int fa, int de) {dep[u] = de, f[u][0] = fa;for(int i=1; i<=30; i++)f[u][i] = f[f[u][i-1]][i-1];for(auto v : g[u]) {if(v == fa) continue;dfs1(v, u, de+1);}
}int LCA(int x, int y){if(dep[x]<dep[y]) swap(x, y);for(int i=30; i>=0; i--)if(dep[f[x][i]]>=dep[y])x = f[x][i];if(x == y) return x;for(int i=30; i>=0; i--)if(f[x][i] ^ f[y][i])x=f[x][i], y=f[y][i];return f[x][0];
}void dfs2(int u, int fa) {for(auto v : g[u]) {if(v == fa) continue;dfs2(v, u);a[u].x += a[v].x;a[u].y += a[v].y;}a[u].x -= 2ll * a[u].y;
}void dfs3(int u, int fa, ll num) {ans[u] = num;for(auto v : g[u]) {if(v == fa) continue;dfs3(v, u, num - a[v].x);}
}int main() {scanf("%d%d", &n, &m);for(int i=1, u, v; i<n; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs1(1, 0, 1);while(m--) {ll u, v, lca, len;scanf("%lld%lld", &u, &v);lca = LCA(u, v);len = dep[u] + dep[v] - 2ll * dep[lca];a[u].x += len + 1, a[u].y += 1;a[lca].x -= len + 1 - 2ll * (dep[u] - dep[lca]), a[lca].y -= 1;a[v].x += len + 1, a[v].y += 1;a[lca].x -= len + 1 - 2ll * (dep[v] - dep[lca]), a[lca].y -= 1;ans[1] += 1ll * (dep[u] - dep[lca]) * (dep[v] - dep[lca]);}dfs2(1, 0);dfs3(1, 0, ans[1]);for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}