//virtual tree
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define TS cout<<"!!!"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + , gakki = + + + + 1e9;
const int MAXN = 3e5 + , MAXM = 3e5 + , MAXQ = , INF = 1e9;
const ll LLINF = (1LL << );
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], tot = ;
inline void addedge(int u, int v) {
if (u == v) {
return ;
}
to[++tot] = v;
nxt[tot] = Head[u];
Head[u] = tot;
}
template <typename T> inline void read(T&x) {
char cu = getchar();
x = ;
bool fla = ;
while (!isdigit(cu)) {
if (cu == '-') {
fla = ;
}
cu = getchar();
}
while (isdigit(cu)) {
x = x * + cu - '', cu = getchar();
}
if (fla) {
x = -x;
}
}
int n;
int jumpfa[MAXN][];
int sz[MAXN];
int dfn[MAXN], deep[MAXN];
int cnt = ;
int top;
int s[MAXN];
int k[MAXN], k2[MAXN];
bool del[MAXN];
void dfs1(int x, int fa) {
jumpfa[x][] = fa;
dfn[x] = ++cnt;
sz[x] = ;
for (int i = ; i <= ; i++) {
jumpfa[x][i] = jumpfa[jumpfa[x][i - ]][i - ];
}
for (int v, i = Head[x]; i; i = nxt[i]) {
if (v = to[i], v != fa) {
deep[v] = deep[x] + ;
dfs1(v, x);
sz[x] += sz[v];
}
}
}
inline int lca(int x, int y) {
if (deep[x] < deep[y]) {
swap(x, y);
}
int t = ;
while (( << t) <= deep[x]) {
t++;
}
t--;
for (int i = t; i >= ; i--) {
if (deep[x] - ( << i) >= deep[y]) {
x = jumpfa[x][i];
}
}
if (x == y) {
return x;
}
for (int i = t; i >= ; i--) {
if (jumpfa[x][i] != jumpfa[y][i]) {
x = jumpfa[x][i], y = jumpfa[y][i];
}
}
return jumpfa[x][];
}
inline bool cmp(int a, int b) {
return dfn[a] < dfn[b];
}
inline void insert_point(int x) {
if (top == ) {
s[++top] = x;
return ;
}
int grand = lca(x, s[top]);
if (grand == s[top]) {
s[++top] = x;
return ;
}
while (top >= && dfn[s[top - ]] >= dfn[grand]) {
addedge(s[top - ], s[top]);
top--;
}
if (grand != s[top]) {
addedge(grand, s[top]);
s[top] = grand;
}
s[++top] = x;
}
int getpoint(int x, int depcha) {
int aim = x;
for (int i = ; i >= ; i--) {
if (( << i) <= depcha) {
depcha -= ( << i);
aim = jumpfa[aim][i];
}
}
return aim;
}
int getdis(int x, int y) {
return deep[x] + deep[y] - * deep[lca(x, y)];
}
int belong[MAXN];
int ans[MAXN], rest[MAXN];
void getbelong1(int x, int fa) {
rest[x] = sz[x];
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) {
continue;
}
int aim;
aim = getpoint(v, deep[v] - deep[x] - );
rest[x] -= sz[aim];
getbelong1(v, x);
if (belong[v] == ) {
continue;
}
if (belong[x] == ) {
belong[x] = belong[v];
} else {
int dis1, dis2;
dis1 = getdis(x, belong[x]), dis2 = getdis(x, belong[v]);
if (dis1 > dis2 || (dis1 == dis2 && belong[x] > belong[v])) {
belong[x] = belong[v];
}
}
}
}
void getbelong2(int x, int fa) {
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) {
continue;
}
if (belong[v] == ) {
belong[v] = belong[x];
} else {
int dis1, dis2;
dis1 = getdis(v, belong[x]), dis2 = getdis(v, belong[v]);
if (dis1 < dis2 || (dis1 == dis2 && belong[v] > belong[x])) {
belong[v] = belong[x];
}
}
getbelong2(v, x);
}
}
void getans(int x, int fa) {
int aim, now;
ans[belong[x]] += rest[x];
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) {
continue;
}
getans(v, x);
if (deep[v] - deep[x] == ) {
continue;
}
if (belong[x] == belong[v]) {
aim = getpoint(v, deep[v] - deep[x] - );
ans[belong[x]] += sz[aim] - sz[v];
} else {
now = v;
for (int i = ; i >= ; i--) {
aim = jumpfa[now][i];
if (deep[aim] <= deep[x]) {
continue;
}
int dis1, dis2;
dis1 = getdis(aim, belong[x]), dis2 = getdis(aim, belong[v]);
if (dis1 > dis2 || (dis1 == dis2 && belong[x] > belong[v])) {
now = aim;
}
}
aim = getpoint(v, deep[v] - deep[x] - );
ans[belong[x]] += sz[aim] - sz[now];
ans[belong[v]] += sz[now] - sz[v];
}
}
}
void init(int x, int fa) {
for (int i = Head[x]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) {
continue;
}
init(v, x);
}
Head[x] = belong[x] = ;
}
int main() {
int u, v;
read(n);
for (int i = ; i <= n - ; i++) {
read(u), read(v);
addedge(u, v);
addedge(v, u);
}
deep[] = ;
dfs1(, );
mem(Head, );
int m, number, xxx;
read(m);
while (m--) {
tot = ;
top = ;
read(number);
xxx = number;
for (int i = ; i <= number; i++) {
read(k[i]);
k2[i] = k[i];
del[k[i]] = ;
belong[k[i]] = k[i];
}
if (belong[] == ) {
k[++number] = ;
}
sort(k + , k + number + , cmp);
for (int i = ; i <= number; i++) {
insert_point(k[i]);
}
while (top > ) {
addedge(s[top - ], s[top]);
top--;
}
getbelong1(, );
getbelong2(, );
// for (int i = 1; i <= n; i++) {
// cout << rest[i] << " ";
// }
// cout << endl;
// for (int i = 1; i <= n; i++) {
// cout << belong[i] << " ";
// }
// cout << endl;
getans(, );
printf("%d", ans[k2[]]);
for (int i = ; i <= xxx; i++) {
printf(" %d", ans[k2[i]]);
}
puts("");
init(, );
for (int i = ; i <= number; i++) {
del[k[i]] = ;
ans[k[i]] = ;
}
}
return ;
}

最新文章

  1. 如何解决插入Oracle数据中文为乱码问题
  2. JavaScript 数据类型判断
  3. Leetcode #28. Implement strStr()
  4. URL后面带\斜杠对SEO的影响
  5. 反射调用与Lambda表达式调用
  6. JavaScript学习笔记(12)——JavaScript自定义对象
  7. 【Qt】数据库连接池
  8. redis参考
  9. VPS用LNMP安装WordPress
  10. maven在mac上的入门使用
  11. iOS学习心得——UITableViewCell的复用
  12. 解决.Net MVC EntityFramework Json 序列化循环引用问题.
  13. 读书笔记—CLR via C#线程27章节
  14. 【ios开发】自定义Actionsheet实现时间选择器和省市区选择器
  15. CodeForces Round #555 Div.3
  16. POM文件详解(2)
  17. shell 中let无法使用的原因
  18. C++中模板的特化与偏特化
  19. 2017-2018 Exp9 网络欺诈技术防范 20155214
  20. java学习笔记—ServletConfig、ServletContext接口(13)

热门文章

  1. DRF视图-请求与响应
  2. 【AMAD】cookiecutter-django -- 是一个构建Django项目的脚手架工具
  3. 【VS开发】使用VS2010创建MFC ActiveX工程项目
  4. Java学习笔记-反射机制
  5. linux的route
  6. [AcWing30]正则表达式匹配
  7. Redis 是怎么实现 “附近的人” 的?
  8. Luogu P4426 [HNOI/AHOI2018]毒瘤
  9. VC++2017关于项目出现&quot;const char *&quot; 类型的实参与 &quot;char *&quot; 类型的形参不兼容错误的解决方法
  10. DevOps 之 Jenkins 安装、配置、美化、插件及常见错误处理