如题，我的思路是对蓝色树进行点分治，在以节点 $root$ 为根时，钦定红色树上的 $root$ 节点也是根节点，然后求出红色树上每个节点的父亲，如果 $i$ 在红树上父亲为 $p_i$，那么让蓝色树上的 $i$ 节点标记一个 $p_i$，题目转换为求蓝色树上的一条过 $root$ 的链，满足链上每一个节点(除了 $root$)的标记点都同样在链上。

为了解决这个问题，对于蓝树上的每一个点 $u$，找出它作为链条的一端时，这些节点的标记点的分布情况。某个点可以成为链条的一端当且仅当这个点到 $root$ 的所有点的标记点全部分布于这条链本身和另外的某一条链上。定义 $other[i]$ 表示 $i$ 到 $root$ 的路径上，出现在链外的标记点中深度最深的一个。（那么显然所有标记点必须是 $other[u]$ 的祖先或 $u$ 的祖先，$u$ 才能成为某根链条的一端）。$u$ 到 $root$ 的链对答案的贡献就是 $other[u]$ 的子树里有多少个点 $v$ 满足 $other[v]$ 是 $u$ 的祖先。

所以现在需要处理 $O(n)$ 个问讯，每个问讯形如:求点 $i$ 的子树中多少个点 $v$ 满足 $other[v]$ 是 $u$ 的祖先。这些问讯可以通过线段树合并实现。

理论时间复杂度 $O(nlog^2n)$，但是因为常数过于巨大，只能通过 1~4, 8~10的测试点。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace fast_IO{//快读模板
    #define FASTIO
    #define IOSIZE 100000
    char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
    #ifdef ONLINE_JUDGE
    #define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
    #define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif
    #define isdigit(ch)(ch>47&&ch<58)
    #define isspace(ch)(ch<33)
    template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}
    #ifdef _GLIBCXX_STRING
    inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
    #endif
    template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
}using namespace fast_IO;
#define rep(i, a, b) for(ll i=a;i<=b;i++)
const ll N=1e5+9;
ll T, n, res;
vector <ll> to1[N], to2[N];
bool vst[N];
bool con[N];//con[i]表示i和当前的root在1树上是否连通
ll lin[N];//lin[i]表示和i有联系的点的编号
void dfs_on_1(ll u, ll fa, bool clear=0){//在1树上计算con和lin数组
    if(clear==0){
        con[u]=1;
        lin[u]=fa;
    }else{
        con[u]=lin[u]=0;
    }
    for(ll v:to1[u]){
        if(v==fa)continue;
        if(vst[v])continue;
        dfs_on_1(v, u, clear);
    }
}
ll timer, in[N], out[N];
void dfs_2_find_in_out(ll u, ll fa){//在2树上计算in和out数组
    in[u]=++timer;
    for(ll v:to2[u]){
        if(vst[v]||v==fa)continue;
        dfs_2_find_in_out(v, u);
    }
    out[u]=timer;
}
bool belong(ll u, ll v){//判断在2树上，u是否属于v的子树
    return in[u]>=in[v]&&out[u]<=out[v];
}
vector <ll> ques[N];//ques[i]存储所有关于i的子树的问讯,询问i的子树里有多少个可行点的othe包含
ll othe[N];//othe存储所有可行点的otherEnd,othe[i]是0表示这个点不是可行点
void dfs_2_find_target(ll u, ll fa, ll branch, ll uEnd, ll otherEnd, ll root){//branch表示当前节点属于root的哪一个儿子的子树，uEnd表示在u这个分支上最深的关联点，otherEnd表示在u的其他分支上最深的关联点
    if(con[u]==0)return;
    if(belong(lin[u], branch)){
        if(belong(lin[u], uEnd)){
            uEnd=lin[u];
        }else if(belong(uEnd, lin[u])){
            //什么都不用做
        }else{
            return;
        }
    }else{
        if(belong(lin[u], otherEnd)){
            otherEnd=lin[u];
        }else if(belong(otherEnd, lin[u])){
            //什么都不用做
        }else{
            return;
        }
    }
    if(belong(u, uEnd)){
        // 当心otherEnd==root的情况
        //u是可行的，可以作为一条链条的端点，那么应该求出otherEnd的子树里有多少个的可行点的otherEnd包含u，然后答案加上这个数
        ques[otherEnd].emplace_back(u);
        if(otherEnd==root){//如果otherEnd是root，那么可能产生u和自己本分支的点匹配的情况，需要扣除
            ques[branch].emplace_back(-u);//-u的含义和u类似，但是表示这个问讯的答案应该被从ans中减去
        }
        othe[u]=otherEnd;
    }
    for(ll v:to2[u]){
        if(vst[v]||v==fa)continue;
        dfs_2_find_target(v, u, branch, uEnd, otherEnd, root);
    }
}

struct segment_tree{
    ll nN;
    struct point{
        ll ls, rs, ad;
    }tr[N*33];
    inline ll merge(ll u, ll v){
        if(u*v==0)return u+v;
        tr[u].ad+=tr[v].ad;
        tr[u].ls=merge(tr[u].ls, tr[v].ls);
        tr[u].rs=merge(tr[u].rs, tr[v].rs);
        return u;
    }
    inline ll add(ll u, ll l, ll r, ll x, ll z, ll y){
        if(u==0){u=++nN;tr[u].ls=tr[u].rs=0;tr[u].ad=0;}
        if(l<=z&&r>=y){tr[u].ad+=x;return u;}
        if(l>y||r<z)return u;
        ll mid=((z+y)>>1);
        tr[u].ls=add(tr[u].ls, l, r, x, z, mid);
        tr[u].rs=add(tr[u].rs, l, r, x, mid+1, y);
        return u;
    }
    inline ll query(ll u, ll x, ll z, ll y){
        if(u==0)return 0;
        if(z==y)return tr[u].ad;
        ll mid=((z+y)>>1);
        if(x<=mid){
            return query(tr[u].ls, x, z, mid)+tr[u].ad;
        }else{
            return query(tr[u].rs, x, mid+1, y)+tr[u].ad;
        }
    }
}tree;
ll ans=0;
ll dfs_2_find_ans(ll u, ll fa){//解决ques中的问讯，并把答案累加到ans上，同时返回它对应的线段树的根
    // tree.nN++;//新建立一颗线段树
    if(con[u]==0)return 0;
    ll id=0;
    for(ll v:to2[u]){
        if(v==fa||vst[v])continue;
        id=tree.merge(id, dfs_2_find_ans(v, u));
    }
    if(othe[u]){
        id=tree.add(id, in[othe[u]], out[othe[u]], 1, 1, timer);
    }
    for(ll q:ques[u]){
        ans+=tree.query(id, in[abs(q)], 1, timer)*(q>0?1:-1);
    }
    return id;
}
void dfs_2_clear(ll u, ll fa){
    ques[u].clear();othe[u]=0;in[u]=out[u]=0;
    for(ll v:to2[u]){
        if(v==fa||vst[v])continue;
        dfs_2_clear(v, u);
    }
}
void calc(ll root){
    //2树上，统计过root的路径
    ans=0;
    vst[root]=1;
    dfs_on_1(root, 0);
    timer=0;dfs_2_find_in_out(root, 0);
    // return;
    for(ll i=0;i<to2[root].size();i++){
        ll v=to2[root][i];
        dfs_2_find_target(v, root, v, v, root, root);
    }   
    othe[root]=root;//root也算可行点（因为它可以作为链条的一端）
    ques[root].emplace_back(root);
    dfs_2_find_ans(root, 0);
    ans++;//加上root~root这一条链
    ans/=2;//一个链会被链条的两个端点贡献两次，所以要除以二
    res+=ans;
    dfs_on_1(root, 0, 1);
    dfs_2_clear(root, 0);
    tree.nN=0;
}
ll sz[N];
ll center, maxson;
void dfs_2_find_center(ll u, ll fa, ll szAll){
    sz[u]=1;
    ll mx=0;
    for(ll v:to2[u]){
        if(v==fa||vst[v])continue;
        dfs_2_find_center(v, u, szAll);
        sz[u]+=sz[v];
        mx=max(mx, sz[v]);
    }
    mx=max(mx, szAll-sz[u]);
    if(mx<maxson){
        maxson=mx;center=u;
    }
}
void solve(ll u){
    calc(u);
    for(ll v:to2[u]){
        if(vst[v])continue;
        maxson=1e8;dfs_2_find_center(v, u, sz[v]);
        
        solve(center);
    }
}
int main(){
    ios::sync_with_stdio(false);
    io >> T;
    while(T--){
        io >> n;
        for(ll i=1;i<n;i++){
            ll u, v;io >> u >> v;
            to1[u].emplace_back(v);
            to1[v].emplace_back(u);
        }
        for(ll i=1;i<n;i++){
            ll u, v;io >> u >> v;
            to2[u].emplace_back(v);
            to2[v].emplace_back(u);
        }
        maxson=1e8;dfs_2_find_center(1, 0, n);
        solve(center);
        io << res << '\n';
        res=0;
        rep(i, 1, n){
            to1[i].clear();to2[i].clear();
        }
        fill(vst, vst+n+5, 0);
        fill(sz, sz+n+5, 0);
    }
    return 0;
}