参考博客,看不懂的话可以去这位巨巨的博客看。
题意：给定两棵树，要求一个最大集合，使得集合里的所有元素在第一棵树上都存在祖先关系，在第二棵树上又没有祖先关系。输出这个集合的大小。
思路：我们可以在第一棵树上dfs跑链，这样保证了第一棵树上的祖先关系，每个点在被放入集合的时候，都要判断这个点是否和已经在集合里面的点在第二棵树上构成祖先关系。第二棵树上的祖先关系可以通过DFS序来判断，同时用线段树来维护这个关系，用滑动窗口来维护答案。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=5e5+7;
const double pi=acos(-1);
using namespace std;
int _,n,m,num,u,v;
vector<int > v1[maxn],v2[maxn]; 
int L[maxn],R[maxn];
int tree[maxn<<2],tag[maxn<<2];//4倍空间 
int ls(int rt) { return rt<<1;}
int rs(int rt) { return rt<<1|1;}
void push_up(int rt)
{
    tree[rt]=max( tree[ ls(rt) ] , tree[ rs(rt) ] );
    return ;
}
void push_down(int rt)
{
    if(tag[rt])
    {
        tree[ls(rt)]+=tag[rt];
        tree[rs(rt)]+=tag[rt];

        tag[ls(rt)]+=tag[rt];
        tag[rs(rt)]+=tag[rt];

    }
    tag[rt]=0;
}
void build(int rt,int l ,int r)
{
    //清空当前节点
    tree[rt]=0;
    tag[rt]=0;
    if(l==r) // 叶子结点 
    {
        return ;
    } 
    int mid = ( l+r ) >> 1;
    build( ls(rt) , l , mid );
    build( rs(rt) , mid+1 , r );
    push_up(rt);
}
void update ( int LL, int RR ,int rt ,int k=1 , int l=1,int r =n)
{
    if(LL>r  || RR <l )
    {
        return ;
    }
    if(LL<=l && r <= RR)//当前区间小于等于需要修改的区间 
    {
        tree[rt]+=k;
        tag[rt]+=k;
        return ;    
    } 
    push_down(rt);
    int mid = ( l+r ) >> 1;
    if(mid>=LL) 
        update( LL , RR , ls(rt) ,k ,l,mid);
    if(mid<RR)
        update( LL , RR , rs(rt) ,k ,mid+1,r);
    push_up(rt);    
}
void dfn(int rt,int fa=0)//第二棵树的DFS序 
{
    L[rt]=++num;
    for(int i=0,sz=v2[rt].size();i<sz;i++)
    {
        if(v2[rt][i]!=fa)
        {
            dfn(v2[rt][i] , rt);
        }
    }
    R[rt]=num;
}
//线段树上做滑动窗口
int stk[maxn];
int top;
int bot;
int ans;
void dfs(int rt,int fa)
{
    int now = -1;
    stk[++top] = rt;//这个点进入滑动窗口
    update(L[rt],R[rt],1,1);//第一个1 是 根节点， 第二个一 表示要给这个区间的访问次数加一 
    if(tree[1]==1)//不存在被访问2次以上的点 , 符合条件 
    {
        ans=max(ans,top-bot+1);
    }
    else if ( top-bot+1 > ans)
    {
        //滑动窗口， 丢掉最先进入滑动窗口的点
        now = stk[bot++];//注意两种自增运算，这是后自增
        update(L[now],R[now],1,-1);//撤销这个点的影响         
    } 
    //去往下一个点 
    for(int i=0,sz=v1[rt].size();i<sz;i++)
    {
        int q=v1[rt][i];
        if(q!=fa)
            dfs(q,rt);
    }
    //你在return 之前，所有变量还原成进来的样子 
    if(now!=-1)
    {
        update(L[now],R[now],1,1);
        stk[--bot] = now;
    }
    //这个也是还原 
    update(L[rt],R[rt],1,-1);
    top--;//假装没进过这个点 

}
void init()
{
    bot=0;
    top=-1;
    ans=1;
    memset(stk,0,sizeof(stk)); 
    num=0;
     for(int i = 1;i <= n;i ++) 
     v1[i].clear(),v2[i].clear();
}
int main()
{
    for(cin>>_;_;_--){
        init();
        cin>>n;
        build(1,1,n);
        for(int i=1;i<n;i++)
        {
            cin>>u>>v;
            v1[u].push_back(v);
            v1[v].push_back(u);
        }
        for(int i=1;i<n;i++)
        {
            cin>>u>>v;
            v2[u].push_back(v);
            v2[v].push_back(u);
        }
        dfn(1);//对第二棵树做dfs序
        dfs(1,0);
        cout<<ans<<endl;
    }
    return 0;
}

顺十字的线段树需要加强啊