[NOI2020] 命运

前置：线段树合并（线段树应用之一，建议先把yxc老师讲的线段树彻底搞清楚）

建议先做 Minimax

本题解参考网络上大部分做法，加上自己的理解。

还是从正常的考场思路来看吧。
题目大意就是说你可以给所有的边赋边权 $0/1$ 但需要满足题目给的 $m$ 条链接儿子祖先的链上至少有一条边为 $1$ 。
（以下的为一个点赋值就是指对他连向他父亲的边赋值，本质相同）

第一眼看到他，你会想到几种计数方式。
有一种就是你可以强制一条边他必须选上，那么我们需要枚举子树里面上次选的点有哪些，也就是直接枚举儿子集合，看看这个方案行不行暴力统计。
显然这样子复杂度是不正确的，并且，根据子树内的点选择状态上传统计答案的方式并不可取，因为要不复杂度不对，要不太麻烦了。
（不过我看了看网上还是有这样子过了的。。。。可能是我太菜想不到吧。

然后我们考虑更换一种方式进行统计答案。
比如说，我们可以枚举一个点上方祖先的赋 $1$ 情况。
这样为什么好做一些呢？因为我们会发现选择点的集合都是严格固定在他的祖先链上的。

那我们考虑怎么 $DP$ 计数，显然固定树结构的计数用多项式的不常见，除了部分神题依赖于树结构方案进行组合。
你想，如果有一个节点 $u$ ，他的某个祖先 $p$ 被赋值，那么越过 $u$ 和 $p$ 的限制一定会获得满足，并且此时包含该限制链的限制链也一定能获得满足。

那么我们可以考虑枚举设 $f_{u,i}$ 表示对于所有下端位于 $u$ 子树内限制链，这些限制链的最深深度位于 $i$ 的状态下我们的方案数。

你想，这个时候我们必须要把 $u$ 的深度位 $i$ 或者小于 $i$的点选掉至少一个，这样这些限制链就都满足了。

考虑怎么 $DP$ 合并子树信息进行统计。

第一种情况， 我们让这个 $u$ 的深度为 $i$ 的祖先选上，那么此时他的儿子们随便选什么祖先都行，反正这些限制链都能满足，这时的贡献是：

$$f_{u,i}=\sum_{k=0}^{depth_u}\ f_{u,i}\times f_{v,k}$$

但如果这个 $u$ 的深度为 $i$ 的祖先没有被选择呢？我们只能通过他的儿子们来满足了。
此时，他的儿子们必须满足他们的选的最深的祖先深度必须低于 $u$ 的这个没有被选的祖先，这意味着他的儿子们已经能够让 $u$ 的这个祖先满足条件，这样才能让这些限制链满足，所以说这稍有一个点选的祖先深度 $=i$。

$$f_{u,i}=\sum_{k=0}^{i}\ f_{u,i}\times f_{v,k}\ +\ \sum_{k=0}^{i-1}\ f_{v,i}\times f_{u,k}$$

上指标 $i-1$ 是减掉算重。

显然这样是 $O(n^2)$ 的猛复杂度，考虑怎么优化。

回到了开篇推的那道题。

把 $f_{u,i}$ 放在 $u$ 所在那个线段树的 $pos\ i$ ，每次转移是取前缀转移。

因此就是线段树合并优化 $DP$

不要抄，我的常数很大。

Code:

#include<cstdio>
#include<vector>
#include<utility>
#include<iostream>
#define mp make_pair
#define P pair<int,int>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
typedef long long LL;
const LL mod=998244353;
const int N=5e5+5;
inline int getint()
{
    char c;int f=0;
    while(c=getchar(),c>'9' || c<'0');
    while(f=(f<<1)+(f<<3)+c-'0',c=getchar(),c>='0' && c<='9');
    return f;
}
int n,m;
int deep[N];
struct Edge{
    int to,next;
}edge[N<<1];
struct Seg{
    int ls,rs,val;
    int tag;
}t[N<<5];
int Root[N];
int sum_edge,head[N];
vector<int> g[N];
int Max_depth,SUM,tot;

inline void Add_edge(int from,int to)
{
    ++sum_edge;
    edge[sum_edge].to=to;
    edge[sum_edge].next=head[from];
    head[from]=sum_edge;
}
inline void Pre_dfs(int u,int pa)
{
    for(register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==pa) continue;
        deep[v]=deep[u]+1;
        Pre_dfs(v,u);
    }
}

inline void Update(int p)
{
    t[p].val=(t[t[p].ls].val+t[t[p].rs].val)%mod;
}
inline void Pushdown(int p)
{
    if(t[p].tag!=1){
        if(t[p].ls){
            t[t[p].ls].val=1ll*t[t[p].ls].val*t[p].tag%mod;
            t[t[p].ls].tag=1ll*t[t[p].ls].tag*t[p].tag%mod;
        }
        if(t[p].rs){
            t[t[p].rs].val=1ll*t[t[p].rs].val*t[p].tag%mod;
            t[t[p].rs].tag=1ll*t[t[p].rs].tag*t[p].tag%mod;
        }
        t[p].tag=1;
    }
}
inline void Modify(int &p,int left,int right,int pos,int val)
{
    if(!p) p=++tot,t[p].tag=1;
    if(left==right) return t[p].val=val,void();
    int mid=left+right>>1;
    if(pos<=mid) Modify(t[p].ls,left,mid,pos,val);
    if(pos>mid) Modify(t[p].rs,mid+1,right,pos,val);
    Update(p);
}
inline int Query(int p,int left,int right,int ql,int qr)
{
    if(!p) return 0;
    if(left>=ql && qr>=right) return t[p].val;
    Pushdown(p);
    int mid=left+right>>1,ans=0;
    if(ql<=mid) ans=(ans+Query(t[p].ls,left,mid,ql,qr))%mod;
    if(qr>mid) ans=(ans+Query(t[p].rs,mid+1,right,ql,qr))%mod;
    return ans;
}
inline P Merge(int &R,int pre_R,int left,int right,int sum1,int sum2)
{
    if(!R && !pre_R) return mp(sum1,sum2);
    if(!pre_R){
        P res=mp((sum1+t[R].val)%mod,sum2);
        t[R].val=1ll*t[R].val*(SUM+sum2)%mod;
        t[R].tag=1ll*t[R].tag*(SUM+sum2)%mod;
        return res;
    }
    if(!R){
        P res=mp(sum1,(sum2+t[pre_R].val)%mod);
        R=pre_R;
        t[R].val=1ll*t[R].val*sum1%mod;
        t[R].tag=1ll*t[R].tag*sum1%mod;
        return res;
    }
    if(left==right){
        P res=mp((sum1+t[R].val)%mod,(sum2+t[pre_R].val)%mod);
        t[R].val=(1ll*t[R].val*(1ll*SUM+sum2+t[pre_R].val)%mod+1ll*t[pre_R].val*sum1%mod)%mod;
        return res;
    }
    Pushdown(pre_R);
    Pushdown(R);
    int mid=left+right>>1;
    P res=Merge(t[R].ls,t[pre_R].ls,left,mid,sum1,sum2);
    res=Merge(t[R].rs,t[pre_R].rs,mid+1,right,res.first,res.second);
    Update(R);
    return res;
}
inline void Build_dfs(int u,int pa)
{
    int maxx=0;
    for(vector<int>::iterator it=g[u].begin();it!=g[u].end();++it)
        maxx=max(maxx,deep[(*it)]);//,cerr<<u<<"  ->  "<<(*it)<<endl;
    Modify(Root[u],0,Max_depth,maxx,1);
    for(register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==pa) continue;
        Build_dfs(v,u);
    }
}
inline void Print(int p,int left,int right)
{
    cerr<<"t["<<p<<"] ["<<left<<","<<right<<"] .val= "<<t[p].val<<" tag= "<<t[p].tag<<endl;
    if(left==right) return;
    Pushdown(p);
    int mid=left+right>>1;
    if(t[p].ls) Print(t[p].ls,left,mid);
    if(t[p].rs) Print(t[p].rs,mid+1,right);
}
inline void Solve(int u,int pa)
{
    for(register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==pa) continue;
        Solve(v,u);
        SUM=Query(Root[v],0,Max_depth,0,deep[u]);
        Merge(Root[u],Root[v],0,Max_depth,0,0);
    }
//  cerr<<"Root["<<u<<"]:\n";Print(Root[u],0,Max_depth);cerr<<endl;
}
int main()
{
    n=getint();
    for(register int i=1,x,y;i<n;++i){
        x=getint(),y=getint();
        Add_edge(x,y);
        Add_edge(y,x);
    }
    deep[1]=1;
    Pre_dfs(1,0);
    for(register int i=1;i<=n;++i) Max_depth=max(Max_depth,deep[i]);
    ++Max_depth;
    m=getint();
    int u,v;
    while(m--){
        u=getint(),v=getint();
        g[v].push_back(u);
    }
    Build_dfs(1,0);

    Solve(1,0);
    printf("%d\n",Query(Root[1],0,Max_depth,0,0));
    return 0;
}