1 条题解

  • 0
    @ 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
    上传者