题目链接：点击打开链接
题意：
给定n个点的树。
下面m个操作，每次给一条路径上的边都染一次。
最后问：每个边被染色的次数。
和去年网赛的一道差不多，就是类似前缀和的做法，
我们在某个点+1然后从叶子节点到根节点求一个前缀和，这样某个点加1就相当于某个点到根的路径都加了1.
所以当我们给[u,v]染色时就 sum[u]++; sum[v]++; sum[LCA(u,v)]-=2;
再把重复的部分减掉即可。
最后求个前缀和。
#include <cstdio>#include <vector>#include <algorithm>#include <iostream>#include <map>#include <set>#include <queue>#include <cstring>#include <cmath>#include <string>using namespace std;typedef pair<int, int> pii;typedef long long ll;const int inf = 1e9;const int mod = 1e9+7;const int N = 5*100001;const int M = 20050;template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x *= -1;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}struct Edge{int from, to, nex, id;Edge(int f = 0, int t = 0, int n = 0, int i = 0) :from(f), to(t), nex(n), id(i){}}edge[N << 1];int head[N], edgenum;void add(int u, int v, int id){Edge E = { u, v, head[u], id };edge[edgenum] = E;head[u] = edgenum++;}int fa[N][20], dep[N], dis[N], edge_id[N];void bfs(int root){queue<int> q;fa[root][0] = root; dep[root] = 0; dis[root] = 0;q.push(root);while (!q.empty()){int u = q.front(); q.pop();for (int i = 1; i<20; i++)fa[u][i] = fa[fa[u][i – 1]][i – 1];for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to;if (v == fa[u][0])continue;edge_id[edge[i].id] = v;dep[v] = dep[u] + 1; dis[v] = dis[u] + 1; fa[v][0] = u;q.push(v);}}}int Lca(int x, int y){if (dep[x]<dep[y])swap(x, y);for (int i = 0; i<20; i++)if ((dep[x] – dep[y])&(1 << i))x = fa[x][i];if (x == y)return x;for (int i = 19; i >= 0; i–)if (fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];return fa[x][0];}int n, q;void input(){rd(n);memset(head, -1, sizeof head); edgenum = 0;for (int i = 1, u, v; i < n; i++){rd(u); rd(v); add(u, v, i); add(v, u, i);}rd(q);}int ans[N], val[N];void put(){for (int i = 1; i < n; i++)printf("%d ", val[edge_id[i]]); puts("");}void dfs(int u, int fa){for (int i = head[u]; ~i; i = edge[i].nex){int v = edge[i].to; if (v == fa)continue;dfs(v, u);val[u] += val[v];}}int main() {input();bfs(1);memset(val, 0, sizeof val);while (q–){int u, v; rd(u); rd(v);val[u]++; val[v]++;val[ Lca(u, v) ] -= 2;}dfs(1, 1);put();return 0;}/*141 21 31 42 1313 143 1010 1210 114 55 95 86 46 7131 71 141 121 111 91 85 127 1114 89 36 104 143 1012 13*/
，别小看任何人，越不起眼的人。往往会做些让人想不到的事。
