2025年北京市大学生程序设计竞赛暨“小米杯”全国邀请赛——D

传送门：https://codeforces.com/gym/105851

题目大意:给定两个树S，T询问有多少点对(x,y) 在两棵树上的 LCA 相同
考虑在S树上进行树上启发式合并,大的集合叫 $L$, 小的叫$R$ ，以$T$ 树的dfn序为下标维护树状数组, 对于 $x\in R$ ,首先在 $S$ 树上包含$x$ 的那个集合的其它点和 $x$ 都不会产生贡献，因为他们的LCA 最高也只是我当前合并的那棵子树根节点 $rt$ 的儿子，考虑怎么计算，首先我们要预处理出每个节点为根在树状数组的范围（$[l_i,r_i]$），然后我们把已经合并好的大集合都加到树状数组中，答案就加上 $query([l_{rt},r_{rt}])-query([l_y,r_y])$ , $y$ 就是上述包含 $x$ 子树的深度最浅的节点( $rt$ 的儿子)，额外的加上 $(x,y)$ 有一个点 $rt$ 的贡献

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;//第一颗树启发式合并，在第二棵树的范围内，统计每个根节点和要加入的轻儿子产生的贡献
inline int lowbit(int x){return x&-x;
}
int n;
struct BIT{vector<int> tree;void init(int &n){tree.assign(n*2+10,0);}void add(int x,int v){for(x;x<tree.size();x+=lowbit(x)) tree[x]+=v;}int query(int x){int ans =0;for(x;x>0;x-=lowbit(x)) ans+=tree[x];return ans;}int ask(int l,int r){return query(r)-query(l-1);}
}tr;constexpr int maxn = 2e5+10;
vector<int> g1[maxn],g2[maxn];
int dfn[maxn],l[maxn],r[maxn],idx =0;
int f[maxn][20],dep[maxn];void update(){for(int j = 1;j<20;++j){for(int i = 1;i<=n;++i){f[i][j] = f[f[i][j-1]][j-1];}}
}
int jump(int x,int h){for(int i = 0;i<20;++i) if((h>>i)&1) x = f[x][i];return x;
}void dfs(int x,int fa){l[x]= dfn[x] = ++idx;dep[x] = dep[fa]+1;f[x][0]=fa;for(auto y:g2[x]){if(y==fa) continue;dfs(y,x);l[x] = min(l[x],l[y]);r[x] = max(r[x],r[y]);}r[x] = max(r[x],dfn[x]);}i64 ans=0;
int sz[maxn],son[maxn],HH;
void dfs1(int x,int fa){sz[x] = 1;for(auto &y:g1[x]){if(y==fa) continue;dfs1(y,x);sz[x]+=sz[y];if(sz[y]>sz[son[x]]) son[x]=y;}
}void deal(int x,int fa,int val){tr.add(dfn[x],val);for(auto &y:g1[x]){if(y==fa) continue;deal(y,x,val);}
}void calc(int x,int fa,int rt){if(l[rt]<=l[x]&&r[x]<=r[rt]){int bk = jump(x,dep[x]-dep[rt]-1);//第一棵树包含x的rt的childans+=tr.ask(l[rt],r[rt])-tr.ask(l[bk],r[bk]);}for(auto y:g1[x]){if(y==fa) continue;calc(y,x,rt);}
}void dsu(int x,int fa,int op){for(auto y:g1[x]){if(y==fa||y==son[x]) continue;dsu(y,x,0);}if(son[x]) dsu(son[x],x,1);ans+=tr.ask(l[x],r[x]);//rt=x的贡献tr.add(dfn[x],1);for(auto &y:g1[x]){if(y==fa||y==son[x]) continue;calc(y,x,x);deal(y,x,1);}if(!op) deal(x,fa,-1);
}void solve(){cin>>n;tr.init(n);idx = 0;for(int i = 0;i<=n;++i){l[i]=r[i]=dfn[i]=0;son[i]=0;g1[i].clear();g2[i].clear();}for(int i = 0;i<n-1;++i){int u,v;cin>>u>>v;g1[u].emplace_back(v);g1[v].emplace_back(u);}for(int i = 0;i<n-1;++i){int u,v;cin>>u>>v;g2[u].emplace_back(v);g2[v].emplace_back(u);}dfs(1,0);dfs1(1,0);update();ans =0;dsu(1,0,1);cout<<ans<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;cin>>t;while(t--) solve();return 0;
}