1 条题解
-
0赵青海 (huhe) LV 7 SU @ 2022-8-26 14:06:14
/***************************************** Note : ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 5e5 + 10; const int INF = 0x3f3f3f3f; int head[N],to[N],ne[N],w[N],id; int n , m; int maxx = 0; int def[N] , fa[N][21] , lg[N]; int read() { char c = getchar(); int s = 0; while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') { s = s * 10 + c - 48; c = getchar(); } return s; } void init() { for(int i = 1; i <= n ; i++) lg[i] = lg[i-1] + (i == 1 << lg[i-1]); } void add(int x, int y) { to[++id] = y , ne[id] = head[x] , head[x] = id; } void dfs(int u , int f) { fa[u][0] = f , def[u] = def[f] + 1; for(int i = 1; i <= lg[ def[u]] ; i++) fa[u][i] = fa[ fa[u][i-1] ][i-1]; for(int i = head[u] ; i ; i = ne[i]) { int v = to[i]; if(v != f) dfs(v,u); } } int lca(int x , int y) { if(def[x] < def[y]) swap(x,y); while(def[x] > def[y]) x = fa[x][ lg[ def[x] - def[y] ] - 1]; if(x == y) return x; for(int i = lg[def[x]] ; i >= 0 ; i--) { if(fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } void dfs1(int s , int f) { int num = 0; for(int i = head[s] ; i ; i =ne[i]) { int v = to[i]; if(v != f) { dfs1(v,s); w[s] += w[v]; } } maxx = max(maxx , w[s]); } int main() { n = read() , m = read(); init(); for(int i = 1,x,y ; i < n ; i ++) { x = read() , y = read(); add(x,y) , add(y, x); } dfs(1,0); int l ,r ; while(m--) { l = read() , r =read(); int k = lca(l ,r); w[l]++; w[r]++; w[ fa[k][0] ] --; w[k]--; } maxx = 0; dfs1(1, 0); cout << maxx << endl; return 0; }
- 1
信息
- ID
- 2214
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者