看着题解1 写的 ,哪里有问题啊
查看原帖
看着题解1 写的 ,哪里有问题啊
866969
telankesi楼主2023/7/11 20:53
#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int mod = 1000000007;

inline int read()
{
	char ch = getchar();
	int x = 0, f = 1;
	while ((ch > '9' || ch < '0') && ch != '-')
		ch = getchar();
	if (ch == '-')
	{
		f = -1;
		ch = getchar();
	}
	while ('0' <= ch && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int n, m, r, x, y, tot = 0;
const int N = 500005, M = 1000005;
int p[N];
int num[N];
int head[N], to[M], nxt[M];
int dep[N];
int son[N];
void dfs(int x,int y) {
	son[x] = 1;
	dep[x] = dep[y] + 1;
	for (int i = head[x]; i; i = nxt[i]) {
		int v = to[i];
		if (v != y) {
			dfs(v, x);
			son[x] = (son[x] + son[v]) % mod;
		}
	}

	return;
}
int getans(int p) {
	int x = son[p];
	int y;
	int ans = x;
	for (int i = head[x]; i; i = nxt[i]) {
		int v = to[i];
		if (dep[v] < dep[p])continue;
		y = son[v];
		ans = (ans + (x - y) * y) % mod;
	}
	return ans;
}
void add(int x, int y)
{
	to[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	return;
}

int main()
{
	n = read(); r = read(); m = read();
	for (int i = 1; i < n; i++)
	{
		x = read(); y = read();
		add(x, y); add(y, x);
	}
	dfs(r, r);
	for (int i = 1; i <= m; i++)
	{
		p[i] = read();
		cout << getans(p[i])<<endl;
	}
	

	return 0;
}
2023/7/11 20:53
加载中...