题目在这里
这道题是个非常裸的树上差分。
树上查分就是把两个点之间的路径差分成根到两个点的路径再减去根到lca的路径。
在这道题里面，每次操作两个端点的差c分值+1，lca和lca的父节点的差分值-1，最后把每个子节点的值加到他们的父节点上就可以求出每个点的实际值。
试着画一下图就可以很好的理解。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using namespace std;
const int N = 500005;
int fa[N][21],dep[N*2];
int n, k;
int chef[N*2],num[N*2];
struct edge{
int v,next;
}e[N * 2];
int front[N*2],cnt = 0;
void AddEdge(int u,int v) {
e[++cnt].v = v;
e[cnt].next = front[u];
front[u] = cnt;
}
void dfs(int x,int fx)
{
dep[x] = dep[fx] + 1;
fa[x][0] = fx;
for (int i = 1;(1<<i) <= dep[x]; i++)
if(fa[x][i - 1]!=-1)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for(int i = front[x]; i; i = e[i].next)
{
int v = e[i].v;
if(v != fx)
dfs(v,x);
}
}
int ans = 0;
void dfs1(int x,int fx)
{
num[x] = chef[x];
for (int i = front[x]; i; i = e[i].next)
{
int v = e[i].v;
if(v != fx)
{
if(!num[v]) dfs1(v,x);
num[x] += num[v];
}
}
if(num[x] > ans) ans = num[x];
}
int lca(int x, int y) {
if(dep[x] > dep[y])
swap(x, y);
for (int i = 20; i >= 0; i--)
{
if (dep[x] <= dep[y] - (1<<i))
if(fa[y][i] != -1)
y = fa[y][i];
}
if (x == y) return x;
for (int i = 20; i >= 0; i--)
{
if(fa[x][i] != fa[y][i] && fa[y][i] != -1)
x = fa[x][i], y = fa[y][i];
}
return fa[x][0];
}
int main()
{
int a,b;
scanf("%d%d",&n,&k);
for (int i = 1; i < n; i++)
{
scanf("%d%d", &a, &b);
AddEdge(a,b);
AddEdge(b,a);
}
dfs(1, -1);
for (int i = 1; i <= k; i++)
{
scanf("%d%d", &a, &b);
// printf("%d\n", lca(a,b));
int xx = lca(a,b);
chef[xx]--;
chef[a]++;
chef[b]++;
if(xx != -1) chef[fa[xx][0]]--;
}
dfs1(1, -1);
printf("%d\n",ans);
return 0;
}