1 条题解

  • 0
    @ 2025-4-16 16:36:53

    换根DP板子题,用换根计算每个点到叶子节点的距离即可。

    时间复杂度:O(n)O(n)

    const int maxn = 2e5 + 7;
    int n, k;
    vector<int> edge[maxn];
    
    int siz[maxn], sum[maxn];
    void dfs(int x, int z)
    {
    	siz[x] = (edge[x].size() == 1);
    	sum[x] = 0;
    	for (int y : edge[x])
    	{
    		if (y == z)
    			continue;
    		dfs(y, x);
    		siz[x] += siz[y];
    		sum[x] += sum[y] + siz[y];
    	}
    }
    
    int dis[maxn];
    void dfs2(int x, int z)
    {
    	if (x != 1)
    		dis[x] = dis[z] + (siz[1] - siz[x]) - siz[x];
    	else
    		dis[x] = sum[x];
    
    	for (int y : edge[x])
    	{
    		if (y == z)
    			continue;
    		dfs2(y, x);
    	}
    }
    
    void solve()
    {
    	cin >> n >> k;
    	for (int i = 1; i < n; i++)
    	{
    		int x, y;
    		cin >> x >> y;
    		edge[x].push_back(y);
    		edge[y].push_back(x);
    	}
    	dfs(1, 0);
    	dfs2(1, 0);
    
    	for (int i = 1; i <= k; i++)
    	{
    		int x;
    		cin >> x;
    		cout << dis[x] << endl;
    	}
    }
    
    • 1

    信息

    ID
    17
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者