【题解】LuoGuU67748：坤链剖分

原题传送门

题目大意：一颗n个节点的树，m个询问(u,v)，每次输出经过了u到v的最短路径的坤链的条数。

首先可以发现的是每个叶子借点都对应着一条坤链。

30%

暴力，对于每一个询问，把u到v的路径上的边打标记，从根节点开始遍历每一条坤链，遍历到叶子节点结束，到叶子结点结束时统计该坤链是否经过了u到v的路径，若是，则统计入答案。

20%
链的情况，送分，发现整棵树只有一个叶子节点，所有只有一条坤链，且该链一定经过任意一条路径，所以对于每个询问，都只要输出1即可。

20%
每个询问的两个端点的lca是根节点的情况。
如果思考这个子任务的话会发现这其实是满分做法的简化版。
可以发现一个有用的性质：边是有深度的（根结点为1），若一条坤链经过一条边，那么该坤链必定经过这条边上面那条边。
举个例子：有两条边1->2,2->3，1为根节点，若一条坤链经过2->3，则该链必定经过1->2
那么，既然两点的lca是1，是不是只要看看有多少坤链经过1连到u，v的第一条边
这个东西可以dfs一遍解决

100%
上一部分的加强版。
首先记录经过每条边的坤链的条数，记录为点的权值，用dfs解决。这里以点代边。
然后处理询问，倍增跳lca，找到lca下两点，那两点的权值之和即为答案。
若两点的lca为其中一点，则只需要lca下一点的权值作为答案。

然后对于如何记录有多少条坤链经过某条边，就是计算这个点的子树中有几个叶子
可以用差分思想，这是我一年半前用的做法
也可以直接统计
Code：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], n, m, d[maxn], fa[maxn][25], val[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

void dfs(int u, int pre){
	d[u] = d[pre] + 1, fa[u][0] = pre;
	val[u] = 1;
	for (int i = 0; fa[u][i]; ++i) fa[u][i + 1] = fa[fa[u][i]][i];
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v == pre) continue;
		dfs(v, u);
		val[u] += val[v];
	}
	if (val[u] > 1) --val[u];
}

int lca(int u, int v){
	if (d[u] < d[v]) swap(u, v);
	for (int i = 20; i >= 0; --i) if (d[fa[u][i]] > d[v]) u = fa[u][i];
	if (fa[u][0] == v)  return val[u];
	if (d[u] > d[v]) u = fa[u][0];
	for (int i = 20; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return val[u] + val[v];
}

int main(){
	n = read(), m = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read();
		addedge(x, y), addedge(y, x);
	}
	dfs(1, 0);
//	for (int i = 1; i <= n; ++i) printf("val[%d] = %d\n", i, val[i]);
	while (m--){
		int x = read(), y = read();
		printf("%d\n", lca(x, y));
	}
	return 0;
}

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int head[maxn], num, d[maxn], fa[maxn][30], tot[maxn], cnt, n, m;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void add_edge(int x, int y){ edge[++num].to = y; edge[num].next = head[x]; head[x] = num; }

void dfs(int u, int pre){
	d[u] = d[pre] + 1; fa[u][0] = pre;
	for (int i = 0; fa[u][i]; ++i) fa[u][i + 1] = fa[fa[u][i]][i];
	int tmp = cnt, flag = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			flag = 1; dfs(v, u);
		}
	}
	cnt += flag == 0;
	tot[u] = cnt - tmp;
}

int query(int u, int v){
	if (d[u] < d[v]) swap(u, v);
	for (int i = 20; i >= 0; --i) if (d[v] + (1 << i) < d[u]) u = fa[u][i];
	if (fa[u][0] == v) return tot[u];
	if (d[u] > d[v]) u = fa[u][0];
	for (int i = 20; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return tot[u] + tot[v];
}

int main(){
	n = read(), m = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read();
		add_edge(x, y); add_edge(y, x);
	}
	dfs(1, 0);
	while (m--){
		int x = read(), y = read();
		printf("%d\n", query(x, y));
	}
	return 0;
}