$\text{Ayano}$ 有一棵 $n$ 个顶点的树（编号从 $1$ 到 $n$ )。 这棵树有 $n-1$ 条边，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 由于$\text{Ayano}$ 非常喜欢这棵树，树上的每条路径都被赋予了价值。具体地，这棵树上长度为 $d$ 的简单路径的价值是 $2^d$。

现在 $\text{Ayano}$ 对你发出了 $q$ 次询问，每次给出两个正整数 $x,y$ ，请你回答所有通过顶点 $x$ 和 $y$ 的简单路径的价值之和 $(\mathrm{mod}998244353)$ 。

注：简单路径是指路径上的各顶点均不互相重复的路径，路径的长度是指一条路径经过的边的条数。

$n\le 10^6$

---

记 $d_u$ 表示 $u$ 到 $1$ 的距离。

预处理出 $su{m}_u=\sum _{v\in T_u}{2}^{d_v-d_u}$。

考虑两种情况

• $x$ 和 $y$ 都不是 $lca$。答案就是 $2^{\mathrm{dis}(x,y)}\sum _{u\in T_x}{2}^{d_u-d_x}\sum _{v\in T_y}{2}^{d_v-d_y}$，直接用 $sum$ 求即可。
• 否则，就要进行换根的操作，令 $x$ 为深度小的那个点，我们想要求以 $x$ 的儿子（往下走可以走到 $y$）为根的 $sum$。简单维护即可。具体可以参照代码。

由于要求 $lca$，我采用树剖的方法，其实可以用 tarjan，我不会。

这里要卡常。

时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+1;
constexpr long long mod=998244353ll;
int n,q;
int head[N],nxt[N<<1],to[N<<1],cnt;
int dep[N],sz[N],fa[N],top[N],son[N];
int sum[N],pw[N],sum1[N];
void add(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
inline int MOD(int x){return x>=mod?x-mod:x;}
void dfs1(int u,int F)
{
    dep[u]=dep[F]+1;
    fa[u]=F;
    sz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        if(to[i]!=F){
            dfs1(to[i],u);
            sz[u]+=sz[to[i]];
            if(sz[son[u]]<sz[to[i]]) son[u]=to[i];
            sum[u]=MOD(sum[u]+sum[to[i]]);
        }
    }
    sum[u]=MOD((sum[u]<<1)+1);
}
void dfs2(int u,int t)
{
    top[u]=t;
    if(son[u]) dfs2(son[u],t);
    for(int i=head[u];i;i=nxt[i]){
        if(to[i]!=fa[u]&&to[i]!=son[u]){
            dfs2(to[i],to[i]);
        }
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]>dep[v]?v:u;
}
void dfs3(int u)
{
    int x=0;
    for(int i=head[u];i;i=nxt[i]) if(to[i]!=fa[u]) x=MOD(x+sum[to[i]]);
    for(int i=head[u];i;i=nxt[i]){
        if(to[i]!=fa[u]){
            sum1[to[i]]=MOD((MOD(MOD(x+sum1[u])+mod-sum[to[i]])<<1)+1);
            dfs3(to[i]);
        }
    }
}
int main()
{
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        add(x,y),add(y,x);
    }
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=MOD(pw[i-1]<<1);
    dfs1(1,0);
    dfs2(1,1);
    dfs3(1);
    cin>>q;
    for(int i=1,x,y;i<=q;i++){
        cin>>x>>y;
        int Lca=lca(x,y);
        if(x!=Lca&&y!=Lca) cout<<1ll*sum[x]*sum[y]%mod*pw[dep[x]+dep[y]-2*dep[Lca]]%mod<<"\n";
        else{
            if(dep[x]>dep[y]) swap(x,y);
            int xx=dep[y]-dep[x]-1,now=y;
            if(xx>0){
                while(top[x]!=top[now]){
                    now=top[now];
                    if(fa[now]==x) goto a;
                    now=fa[now];
                }
                now=son[x];
            }
            a:cout<<1ll*sum[y]*sum1[now]%mod*pw[dep[x]+dep[y]-2*dep[Lca]]%mod<<"\n";
        }
    }
}