或者大佬有没有什么情况会 MLE 的分享一下,谢谢。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, m, u, v, fir[N], nxt[N << 1], son[N << 1], tot, Q, fa[N][20], dep[N], dfsn[N], sum[N][20], sz[N], b[N], a[N], lca, tem, id[N];
int fir2[N], nxt2[N << 1], son2[N << 1], w2[N << 1], to[N], ans[N], f[N], vis[N], TOT[N], now, ttem, SUM, Sum, now1;
//f[i] : the distance of the nearest ; to[i] : the dot of the nearest ; TOT[i] : sz[i] - sigma(sz[son[i]] , son[i] is ancestors to key dots)
inline void add(int x, int y){
nxt[++tot] = fir[x];
fir[x] = tot;
son[tot] = y;
}
inline void add2(int x, int y, int z){
nxt2[++tot] = fir2[x];
fir2[x] = tot;
son2[tot] = y;
w2[tot] = z;
}
inline void dfs(int x, int ff){
sz[x] = 1, dfsn[x] = ++tot, fa[x][0] = ff, dep[x] = dep[ff] + 1;
for(int i = 1; i <= 19; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for(int i = fir[x]; i ; i = nxt[i]){
if(son[i] == ff) continue ;
dfs(son[i], x);
sz[x] += sz[son[i]];
}
}
inline bool cmp(int x, int y){
return dfsn[x] < dfsn[y];
}
inline int LCA(int x, int y){
if(dep[x] > dep[y]) swap(x, y);
for(int i = 19; ~i; i--){
if(dep[fa[y][i]] >= dep[x]) y = fa[y][i];
}
if(x == y) return x;
for(int i = 19; ~i; i--){
if(dep[fa[x][i]] != dep[fa[y][i]]) x = fa[x][i], y = fa[y][i];
}
return fa[x][0];
}
inline void init(){
for(int i = 1; i <= m; i++) fir2[a[i]] = ans[a[i]] = to[a[i]] = TOT[a[i]] = vis[a[i]] = 0, f[a[i]] = 1e9;
m = tot = 0;
}
inline int LCA_son(int x, int y){
if(dep[x] > dep[y]) swap(x, y);
for(int i = 19; ~i; i--){
if(dep[fa[y][i]] > dep[x]) y = dep[fa[y][i]];
}
return y;
}
inline void dp1(int x, int ff){
TOT[x] = sz[x];
if(vis[x]) f[x] = 0, to[x] = x;
for(int i = fir2[x]; i; i = nxt2[i]){
if(son2[i] == ff) continue ;
dp1(son2[i], x);
TOT[x] -= sz[LCA_son(x, son2[i])];
if(f[son2[i]] + w2[i] < f[x]){
f[x] = f[son2[i]] + w2[i];
to[x] = to[son2[i]];
}
else if(f[son2[i]] + w2[i] == f[x]){
to[x] = min(to[x], to[son2[i]]);
}
}
}
inline void dp2(int x, int ff){
for(int i = fir2[x]; i ; i = nxt2[i]){
if(son2[i] == ff) continue ;
if(f[x] + w2[i] < f[son2[i]]){
f[son2[i]] = f[x] + w2[i];
to[son2[i]] = to[x];
}
else if(f[x] + w2[i] == f[son2[i]]){
to[son2[i]] = min(to[x], to[son2[i]]);
}
dp2(son2[i], x);
}
}
inline void dp(int x, int ff){
for(int i = fir2[x]; i ; i = nxt2[i]){
if(son2[i] == ff) continue ;
now = son2[i], SUM = 0;//SUM : 往上跳的步数
ttem = w2[i] - (f[x] - f[son2[i]]) - 1;//中间的点只有 w[i] - 1 个
if(ttem >= 0){
SUM = ttem / 2 + (f[x] - f[son2[i]]);
if(ttem & 1) SUM += (to[son2[i]] <= to[x]);
for(int i = 19; ~i; i--){
if(SUM >= (1 << i)){
Sum -= (1 << i);
now = fa[now][i];
}
}
ans[to[son2[i]]] += sz[now] - sz[son2[i]];
now1 = LCA_son(x, now);
ans[to[x]] += sz[now1] - sz[now];
}
else{
SUM = w2[i] - 1;
for(int i = 19; ~i; i--){
if(SUM >= (1 << i)){
Sum -= (1 << i);
now = fa[now][i];
}
}
ans[to[son2[i]]] += sz[now] - sz[son2[i]];
}
dp(son2[i], x);
}
}
int main(){
memset(f, 63, sizeof(f));
scanf("%d", &n);
for(int i = 1; i < n; i++){
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
tot = 0;
dfs(1, 0);
scanf("%d", &Q);
while(Q--){
init();
scanf("%d", &tem);
for(int i = 1; i <= tem; i++) scanf("%d", &b[i]), vis[b[i]] = 1, id[i] = b[i];
sort(b + 1, b + tem + 1, cmp);
for(int i = 1; i < tem; i++){
a[++m] = b[i];
a[++m] = LCA(b[i], b[i + 1]);
}
a[++m] = b[tem];
a[++m] = 1;
sort(a + 1, a + m + 1, cmp);
m = unique(a + 1, a + m + 1) - a - 1;
for(int i = 1; i < m; i++){
lca = LCA(a[i], a[i + 1]);
add2(lca, a[i + 1], dep[a[i + 1]] - dep[lca]);
}
dp1(1, 0);
dp2(1, 0);
for(int i = 1; i <= m; i++) ans[to[a[i]]] += TOT[a[i]];
dp(1, 0);
for(int i = 1; i <= tem; i++){
printf("%d ", ans[id[i]]);
}
putchar('\n');
}
return 0;
}
/*
10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
1
4
8 7 10 3
*/