题目大意
给你两棵以1为根的树，让你选一个集合，这个集合中的点在第一棵树中互为父子关系，且是连通的，在第二棵树中互相都不是父子关系。
解题思路1
对于第一棵树，很明显集合中的元素在其中是一条链中的一个子段。我们在dfs第一棵树的时候，考虑从根节点1到当前节点u的一条链，链上的的点的深度都是递增的，我们可以往上找一个深度最大的节点p，p和u在第二棵树上是父子关系，那么p到u之间(不包括p)的点和u不是父子关系，但是这些点中也有可能有在第二棵树中有父子关系的点，我们用一个变量max来记录，存储当前链上之前的节点与之冲突的深度最大的点，然后和当前的点取max，max到当前点u的深度之差就是答案。
代码
const int maxn = 3e5+10;
const int maxm = 1e5+10;
vector<int> e[maxn], g[maxn];
int dep[maxn], fa[maxn], sz[maxn], son[maxn];
void dfs1(int u, int p) {
sz[u] = 1;
for (auto v : g[u]) {
if (v==p) continue;
dfs1(v, u);
fa[v] = u;
dep[v] = dep[u]+1;
sz[u] += sz[v];
if (sz[v]>sz[son[u]]) son[u] = v;
}
}
int top[maxn], tim, id[maxn], rev[maxn];
void dfs2(int u, int t) {
top[u] = t;
id[u] = ++tim;
rev[tim] = u;
if (!son[u]) return;
dfs2(son[u], t);
for (auto v : g[u]) {
if (v!=fa[u] && v!=son[u]) dfs2(v, v);
}
}
int n, tr[maxn<<2];
void update(int rt, int l, int r, int pos, int val) {
if (l==r) {
tr[rt] = val;
return;
}
int mid = (l+r)>>1;
if (pos<=mid) update(rt<<1, l, mid, pos, val);
else update(rt<<1|1, mid+1, r, pos, val);
tr[rt] = max(tr[rt<<1], tr[rt<<1|1]);
}
int ask(int rt, int l, int r, int L, int R) {
if (l>=L && r<=R) return tr[rt];
int mid = (l+r)>>1, mx = 0;
if (L<=mid) mx = max(mx, ask(rt<<1, l, mid, L, R));
if (R>mid) mx = max(mx, ask(rt<<1|1, mid+1, r, L, R));
return mx;
}
int query(int u) {
int res = ask(1, 1, n, id[u], id[u]+sz[u]-1);
while(u) {
res = max(res, ask(1, 1, n, id[top[u]], id[u]));
u = fa[top[u]];
}
return res;
}
int ans;
void dfs3(int u, int p, int d, int lst) {
lst = max(lst, query(u));
ans = max(ans, d-lst);
update(1, 1, n, id[u], d);
for (auto v : e[u]) {
if (v==p) continue;
dfs3(v, u, d+1, lst);
}
update(1, 1, n, id[u], 0);
}
void init() {
for (int i = 0; i<=n; ++i) {
e[i].clear(), g[i].clear();
son[i] = 0; tim = 0;
}
}
int main() {
IOS;
int __; cin >> __;
while(__--) {
cin >> n;
for (int i = 1; i<n; ++i) {
int a, b; cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
}
for (int i = 1; i<n; ++i) {
int a, b; cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs1(1, 0);
dfs2(1, 1);
ans = 1;
dfs3(1, 0, 0, 0);
cout << ans << endl;
init();
}
return 0;
}