原题链接

考察:树上差分

思路:

        点差分模板题.定义d[i] 为某路径上经过i的次数.

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 const int N = 50010;
 6 int n,k,h[N],d[N],idx,depth[N],fa[N][16];
 7 struct Road{
 8     int fr,to,ne;
 9 }road[N<<1];
10 void add(int a,int b)
11 {
12     road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;
13 }
14 void bfs(int s)
15 {
16     queue<int> q;
17     q.push(s);
18     memset(depth,0x3f,sizeof depth);
19     depth[s] = 1,depth[0] = 0;
20     while(q.size())
21     {
22         int u = q.front();
23         q.pop();
24         for(int i=h[u];~i;i=road[i].ne)
25         {
26             int v = road[i].to;
27             if(depth[v]>depth[u]+1)
28             {
29                 depth[v] = depth[u]+1;
30                 q.push(v);
31                 fa[v][0] = u;
32                 for(int j=1;j<=15;j++)
33                  fa[v][j] = fa[fa[v][j-1]][j-1];
34             }
35         }
36     }
37 }
38 int lca(int a,int b) 
39 {
40     if(depth[a]<depth[b]) swap(a,b);
41     for(int j=15;j>=0;j--)
42       if(depth[fa[a][j]]>=depth[b]) a = fa[a][j];
43     if(a==b) return a;
44     for(int j=15;j>=0;j--)
45       if(fa[a][j]!=fa[b][j]) a = fa[a][j],b = fa[b][j];
46     return fa[a][0];
47 }
48 void dfs(int u,int fa)
49 {
50     for(int i=h[u];~i;i=road[i].ne)
51     {
52         int v = road[i].to;
53         if(v==fa) continue;
54         dfs(v,u);
55         d[u]+=d[v];
56     }
57 }
58 int main()
59 {
60     scanf("%d%d",&n,&k);
61     for(int i=1;i<=n;i++) h[i] = -1;
62     for(int i=1;i<n;i++)
63     {
64         int a,b;
65         scanf("%d%d",&a,&b);
66         add(a,b); add(b,a);
67     }
68     bfs(1);
69     while(k--)
70     {
71         int a,b; scanf("%d%d",&a,&b);
72         int anc = lca(a,b);
73         d[a]++,d[b]++,d[anc]--,d[fa[anc][0]]--;
74     }
75     dfs(1,-1);
76     int ans = 0;
77     for(int i=1;i<=n;i++) ans = max(ans,d[i]);
78     printf("%d\n",ans);
79     return 0;
80 }