题面
说明/提示
N<=300000, q<=300000,m[1]+m[2]+...+m[q]<=300000
题解
这道题一看 “m[1]+m[2]+...+m[q]<=300000” 就知道可以用虚树做，利用每个关键点和其lca和树根建一棵点数为2 * m[i] - 1的虚树，非关键部分深度为logm，所以我们把关键点们按深度从小到大排序，
我们用dp[x]记录以x为根的子树中深度最小的点，
然后我们发现，每一个点可以一路高攀，访问完没有被访问过的点，然后根据一路分支上的其它子树的dp值，来一路判定势力范围，然后更新答案，每次的复杂度是O(mlogm)。
CODE
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#define LL long long
#define MAXN 300005
using namespace std;
inline int read() {
int f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}
while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}
return x * f;
}
struct ed{
int v,w;
ed(){v = w = 0;}
ed(int V,int W){v = V;w = W;}
};
vector<ed> g[MAXN];
vector<ed> g2[MAXN];
int fa[MAXN][22];
int fu[MAXN];
int pup[MAXN][22];
int d[MAXN],dfn[MAXN],sons[MAXN];
int n,m,i,j,s,o,k,cnt;
LL dp[MAXN][10];
int b[MAXN];
int b2[MAXN];
int b3[MAXN];
bool cmp(int a,int b) {
return dfn[a] < dfn[b];
}
bool cmp2(int x,int y) {
if(d[b[x]] != d[b[y]])return d[b[x]] < d[b[y]];
return b[x] < b[y];
}
void dfs(int x,int fat,int edge) {
dfn[x] = ++cnt;
fa[x][0] = fat;
d[x] = d[fat] + 1;
pup[x][0] = 1;
sons[x] = 1;
for(int i = 1;i <= 19;i ++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
pup[x][i] = 1;
}
for(int i = 0;i < g[x].size();i ++) {
if(g[x][i].v != fat) {
dfs(g[x][i].v,x,g[x][i].w);
int y = g[x][i].v;
sons[x] += sons[y];
}
}
}
void dfsp(int x,int fat) {
pup[x][0] = sons[fat] - sons[x];
for(int i = 1;i <= 19;i ++) {
pup[x][i] = pup[x][i - 1] + pup[fa[x][i - 1]][i - 1];
}
for(int i = 0;i < g[x].size();i ++) {
if(g[x][i].v != fat) {
dfsp(g[x][i].v,x);
}
}
return ;
}
int lca(int a,int b) {
if(d[a] > d[b]) {
for(int i = 19;i >= 0;i --) {
if(d[fa[a][i]] >= d[b]) a = fa[a][i];
}
}
if(d[a] < d[b]) {
for(int i = 19;i >= 0;i --) {
if(d[fa[b][i]] >= d[a]) b = fa[b][i];
}
}
if(a == b) return a;
for(int i = 19;i >= 0;i --) {
if(fa[a][i] != fa[b][i]) {
a = fa[a][i];
b = fa[b][i];
}
}
return fa[a][0];
}
stack<int> st;
int v[MAXN],f[MAXN];
int as[MAXN],asf[MAXN];
void dfs2(int x) {
dp[x][0] = 0;
f[x] = 0;asf[x] = 0;as[x] = 0;
if(v[x]) dp[x][0] = v[x];
for(int i = 0;i < g2[x].size();i ++) {
ed y = g2[x][i];
// printf("%d %d(%lld)\n",x,y.v,y.w);
dfs2(y.v);
fu[y.v] = x;
if(d[dp[y.v][0]] < d[dp[x][0]] || (d[dp[y.v][0]] == d[dp[x][0]] && dp[y.v][0] < dp[x][0])) {
dp[x][0] = dp[y.v][0];
}
}
// printf("%d (%lld %lld)\n",x,dp[x][0],dp[x][1]);
return ;
}
int getsum(int a,int de) {
int ans = 0;
for(int i = 19;i >= 0;i --) {
if(d[fa[a][i]] >= de) ans += pup[a][i],a = fa[a][i];
}
return ans;
}
int getfa(int a,int de) {
for(int i = 19;i >= 0;i --) {
if(d[fa[a][i]] >= de) a = fa[a][i];
}
return a;
}
int dfs3(int x,int fat,int de,int pp) {
f[x] = 1;
// printf("(-%d-)",x);
int ans = sons[x];
for(int i = 0;i < g2[x].size();i ++) {
ed y = g2[x][i];
ans -= sons[y.v] + getsum(y.v,d[x] + 1);
// printf("( (in)ans:%d )",ans);
if(y.v != fat) {
int z = dp[y.v][0];
int nm = de + d[z] - d[x];
int nm2;
if(nm%2) {
nm2 = (nm / 2) - de;
}
else {
nm2 = (nm / 2) - de;
if(pp > z) nm2 --;
}
// printf("( (in)ans:%d nm2:%d nm:%d z:%d )",ans,nm2,nm,z);
if(nm2 < y.w) {
ans += getsum(getfa(y.v,d[x] + nm2 + 1),d[x] + 1);
asf[y.v] = getsum(y.v,d[x] + nm2 + 1);
}
else ans += getsum(y.v,d[x] + 1) + dfs3(y.v,x,de + y.w,pp);
}
}
return ans;
}
void qkdfs(int x) {
for(int i = 0;i < g2[x].size();i ++) qkdfs(g2[x][i].v);
g2[x].clear();return ;
}
int main() {
n = read();
for(int i = 1;i < n;i ++) {
s = read();o = read();
g[s].push_back(ed(o,1));
g[o].push_back(ed(s,1));
}
dfs(1,1,0x7f7f7f7f);
dfsp(1,1);
m = read();
while(m --) {
cnt = read();
for(int i = 1;i <= cnt;i ++) {
b3[i] = b[i] = read();
}sort(b + 1,b + 1 + cnt,cmp);
st.push(1);
for(int i = 1;i <= cnt;i ++) {
v[b[i]] = b[i];
int y1 = st.top();
int lc = lca(y1,b[i]);
int pp = 0,p = 0;
while(!st.empty() && d[st.top()] >= d[lc]) {
pp = p;p = st.top();
st.pop();
if(pp) {
if(pp != p)g2[p].push_back(ed(pp,d[pp] - d[p]));
}
}
if(p && p != lc) {
g2[lc].push_back(ed(p,d[p] - d[lc]));
}
st.push(lc);
st.push(b[i]);
}
int p = 0;
while(!st.empty()) {
int y1 = st.top();
if(p) {
if(p != y1)g2[y1].push_back(ed(p,d[p] - d[y1]));
}
p = y1;
st.pop();
}
d[0] = 0x7f7f7f7f;
dfs2(1);
fu[1] = 0;f[0] = 1;
for(int i = 1;i <= cnt;i ++) b2[i] = i;
sort(b2 + 1,b2 + 1 + cnt,cmp2);
for(int ii = 1;ii <= cnt;ii ++) {
int i = b2[ii];
int p = b[i];
// printf("%d: ",p);
int pp = 0;
while(p) {
as[b[i]] += dfs3(p,pp,d[b[i]] - d[p],b[i]);
// printf("(%d)",as[b[i]]);
if(!f[fu[p]]) {
as[b[i]] += getsum(p,d[fu[p]] + 1);
// printf("([1]%d)",as[b[i]]);
}
else {
as[b[i]] += asf[p];
// printf("([2]%d)",as[b[i]]);
break;
}
pp = p;
p = fu[p];
}
// putchar('\n');
}
for(int i = 1;i <= cnt;i ++) {
printf("%d ",as[b3[i]]);
}putchar('\n');
for(int i = 1;i <= cnt;i ++) v[b[i]] = 0,as[b[i]] = 0;
qkdfs(1);
}
return 0;
}
