自动搬运

查看原文

来自洛谷，原作者为

	Shunpower 我笨笨的，菜菜的，累累的 >_< | 在役

搬运于2025-08-24 22:48:00，当前版本为作者最后更新于2023-04-12 18:12:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\text{upd:}$ 修改了 std 里的一些过于抽象的码风和部分题解表述。

出题人题解。

首先 $\rm Subtask\ 1$ 给了指数级暴搜所有方案然后一一检验的。

实际上真正有启发性的是 $\rm Subtask\ 3,4$，下面我们会提到为什么设置每一个子任务。

下文统一定义 $s_i$ 表示 $i$ 所在子树的大小，${i\choose j}=0$ 如果 $j>i,i<0,j>0$ 三者任占一个。$x_i,y_i$ 的含义同题面所示。

不妨先在最开始算一遍答案。先考虑根是限制点的子树的答案。

下文定义，从某个点向其子树内移动，不用经过别的限制点就能到达的限制点为“顶层限制点”。如果其本身是限制点，不算“顶层限制点”。没有顶层限制点时有 $mul_i=1,cnt_i=0$（这两个变量的具体含义见后文）。

假设这个点是 $i$，首先你需要得到该点为根的子树内所有顶层限制点的答案乘积，显然可以维护，不妨记为 $mul_i$。然后是该点子树内所有顶层限制点的限制 $y$ 之和，显然也很好维护，不妨记为 $cnt_i$。最后是该点子树内所有顶层限制点的子树大小 $siz$ 之和，不妨记为 $ssiz_i$。显然这个点的答案为 $mul_i\times {{s_i-ssiz_i}\choose{y_i-cnt_i}}$。值得注意的是右边的两个减法如果有一个是负值答案都为 $0$。

为了方便，我们下面把点 $i$ 的初始答案称作 $ans_i$。

以上讨论的都是这个根为限制点的情况。对于根为非限制点的，答案即为 $mul_i\times 2^{s_i-ssiz_i}$。而显然，总是存在 $s_i>ssiz_i$。

上文两种情况在没有顶层限制点（整个子树内除了根都没有限制）时仍然正确。

以上的部分主要的就是如何快速处理答案。会这个可以通过 $\rm Subtask\ 1,2$。

下面假设你掌握了处理答案的 $O(siz\log M)$ 以内的做法，其中 $siz$ 是树大小。

现在考虑询问二，容易发现可以在一开始就给每个点都预处理出来询问二的答案。

注意到当点 $i$ 不再是限制点的时候，对于它的父亲，$i$ 的顶层限制点成为 $i$ 父亲的顶层限制点。由于在第一次预处理答案的时候我们对于每一个限制点 $x$ 在算完 $x$ 的答案后要让 $mul_x\leftarrow ans_x,cnt_x\leftarrow y_x,ssiz_i\leftarrow siz_i$ 来方便在树上累积，因此我们考虑存一个 $pmul,pcnt,pssiz$ 表示在改变之前的 $mul,cnt,ssiz$，存留下该点的顶层限制点的各项数据。然后对于预处理询问二答案时，对于限制点儿子我们用 $pmul,pcnt,pssiz$ 去累积、累加（而不是 $mul,cnt,ssiz$），剩余的部分就和预处理普通答案一样。

还可以注意到记忆化询问二的复杂度也是正确的（每个点只会被访问一次）。但出题人十分邪恶，因为询问二的答案可能是 $0$，所以如果记忆化时判断目前答案数组里面是 $0$ 就重算答案会 TLE 在 #21。

会这个可以通过 $\rm Subtask\ 5$。

现在考虑询问一。容易发现我们可以把概率提取出来，也就是 $\frac{1}{c+1}$。然后仍然对于非限制点和限制点分类。

$1'$ 对于非限制点

容易发现其实每次多加一个儿子，就是在给 $k$ 的染色方法数量乘以 $2$，所以甩掉概率后的权值和即为 $ans_k+2^1ans_k+2^2ans_k+2^3ans_k+\cdots+2^{c}ans_k$，直接提取公因数然后做一个等比数列求和，然后乘上概率即可。

做到这里可以通过 $\rm Subtask\ 4$，甚至不需要完全做到这里，处理答案你只需要会非限制点内无限制点的 case 就可以。

$2'$ 对于限制点

容易发现如果一开始 $pmul_k=0$ 或者 $y_k<pcnt_k$ 无论加多少儿子都还会是 $0$。

对于其他情况，可以发现实际上权值和当中的 $pmul_k$ 并不会变，每次变大的只有组合数里面的 $s_k$。为了方便，下面存在 $d_1=y_k-pcnt_k,d_2=s_k-pssiz_k$，所以甩掉概率后的权值和为 $pmul_k\times({{d_2+0}\choose{d_1}}+{C_{d_2+1}\choose{d_1}}+\cdots+{{d_2+c}\choose{d_1}})$。

意思就是说我们要算下面这个式子的值：

$\sum\limits_{i=l}^r {{d_2+i}\choose{d_1}}$，其中 $l$ 我们为了使得组合数不为 $0$，为 $\max (y_k-pcnt_k-s_k+pssiz_k,0)$，$r=c$，特判 $r<l$ 为 $0$。

然而这个式子如果你不会快速算，你可以暴算去通过 $\rm Subtask\ 3$。可以发现，推到这里其实你可以通过 $\rm Subtask\ 1\sim5$，得分可以达到 $80$。下面介绍做这个式子的正解。

根据上指标求和公式有：

$$\sum\limits_{i=0}^n {{i}\choose{m}}={{n+1}\choose{m+1}} $$

于是我们可以把这个和式改成 ${{d_2+r+1}\choose{d_1+1}}-{{d_2+l+1-1}\choose{d_1+1}}$，然后就可以在 $O(\log M)$ 以内的时间复杂度算出来了（$M$ 为模数）。注意右边的组合数可能出现组合数下面大于上面的情况，特判为 $0$。

把这个东西乘上概率和 $pmul_k$ 即可。

上指标求和公式不知道也可以推出，下面是 @StayAlone 的推导：

首先我们推一个 $\sum\limits_{i=0}^n {i\choose m}$。然后利用前缀和相减。

首先你知道 ${{i}\choose{m}}=\frac{i!}{m!(i-m)!}$，在这里你发现 $m$ 是定值（$d_1$），所以先提取 $\frac{1}{m!}$ 到求和外面，然后考虑 $\frac{i!}{(i-m)!}$。然后当你把除法打开变成乘法的时候，你可以发现这是一个极其经典的整数裂项，它的答案为 $\frac{1}{m+1}\prod_{g=n+1-m}^{n+1}g$。

再乘上一个 $\frac{1}{m!}$ 可以得到：

$$\sum\limits_{0\leqslant i\leqslant n} {i\choose m}=\frac{1}{(m+1)!}\prod_{g=n+1-m}^{n+1}g=\frac{1}{(m+1)!}\times\frac{(n+1)!}{(n+1-m-1)!}={{n+1}\choose{m+1}} $$

本质上还是上指标求和，但是可以现场推。后面的方法就和前面一样了。

通过线性预处理阶乘逆元和 $2$ 的次幂，最开始计算答案的时间复杂度为 $O(n)$。再加上线性预处理逆元，询问一复杂度可以做到 $O(1)$。询问二复杂度为 $O(1)$。

最终 std 的复杂度为 $O(n+q)$。数据应该足以把绝大多数错误复杂度卡掉（以及一些常数过分大的 $\log$，简单优化就能过了），正确性写错的应该也基本卡了。不过错法太多，具体出题人也不清楚。/kel/kel/kel

---

下面是 std。

//Author:Leftist / Shunpower
//Spade Su & Griffin BAO
//May the force be with you and me.
#include <bits/stdc++.h>
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define debug puts("--------Chery AK IOI--------");
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define pt puts("")
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define fv(i,p) for(int i=0;i<p.size();i++)
#define ld long double
#define il inline
#define ptc putchar
using namespace std;
const int N=6e5+100;
const ll P=998244353;
namespace Cream_H{
    int lowbit(int x){
        return x&-x;
    }
    template <typename T>
    inline void read(T &x){
       T s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
        }
        x=s*w;
    }
    template <typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9){
            write(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace Cream_H;
int n,m;
int u,v;
vector <int> p[N];
int x,y;
int lim[N];
bool hlim[N];
ll mul[N],cnt[N],ans[N],siz[N],fac[N<<1];
ll pmul[N],pcnt[N],ans2[N],ssiz[N],pssiz[N];
ll pow2[N],invf[N],dpinv[N];
int q;
char opt;
int k,c;
ll allans;
il ll qpow(ll b,ll p,ll k){
    if(!p){
        return 1;
    }
    ll d=qpow(b,p>>1,k);
    if(p&1){
        return d*d%k*b%k;
    }
    else{
        return d*d%k;
    }
}
il void init(int n){
    fac[0]=1;
    pow2[0]=1;
    dpinv[1]=1;
    fr1(i,1,n){
        pow2[i]=pow2[i-1]*2ll;
        pow2[i]%=P;
        fac[i]=fac[i-1]*(ll)i;
        fac[i]%=P;
        if(i!=1){
        	dpinv[i]=((1ll*(-P/i)*dpinv[P%i])%P+P)%P;
		}
    }
    invf[n]=qpow(fac[n],P-2,P);
    fr2(i,n-1,0){
        invf[i]=1ll*invf[i+1]*(i+1)%P;
    }
}
il ll C(ll n,ll m){//m choose n
    if(n<0||m<0||n>m){
        return 0;
    }
    return fac[m]*invf[n]%P*invf[m-n]%P;
}
il void dfs(int x,int fa){
    mul[x]=1;
    siz[x]=1;
    fv(i,p[x]){
        if(p[x][i]==fa){
            continue;
        }
        dfs(p[x][i],x);
        mul[x]*=mul[p[x][i]];
        mul[x]%=P;
        cnt[x]+=cnt[p[x][i]];
        siz[x]+=siz[p[x][i]];
        ssiz[x]+=ssiz[p[x][i]];
    }
    if(hlim[x]){
        ans[x]=mul[x]*C(lim[x]-cnt[x],siz[x]-ssiz[x])%P;
        pmul[x]=mul[x];
        pcnt[x]=cnt[x];
        pssiz[x]=ssiz[x];
        mul[x]=ans[x];
        cnt[x]=lim[x];
        ssiz[x]=siz[x];
    }
    else{
        ans[x]=mul[x]*pow2[siz[x]-ssiz[x]]%P;
        pmul[x]=mul[x];
        pcnt[x]=cnt[x];
        pssiz[x]=ssiz[x];
    }
}
il void dfs2(int x,int fa){
    ll muld=1,cntd=0,sizd=0;
    fv(i,p[x]){
        if(p[x][i]==fa){
            continue;
        }
        dfs2(p[x][i],x);
        muld*=pmul[p[x][i]];
        muld%=P;
        cntd+=pcnt[p[x][i]];
        sizd+=pssiz[p[x][i]];
    }
    if(hlim[x]){
        ans2[x]=muld*C(lim[x]-cntd,siz[x]-sizd)%P;
    }
    else{
        ans2[x]=muld*pow2[siz[x]-sizd]%P;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    init(600050);
    fr1(i,1,n-1){
        cin>>u>>v;
        p[u].pb(v);
        p[v].pb(u);
    }
    fr1(i,1,m){
        cin>>x>>y;
        lim[x]=y;
        hlim[x]=1;
    }
    dfs(1,0);
    dfs2(1,0);
    cin>>q;
    fr1(i,1,q){
        ll qans=0;
        cin>>opt>>k;
        if(opt=='Z'){
        	cin>>c;
            ll div=dpinv[c+1];
            if(!hlim[k]){
                ll muls=pow2[c+1]-1;
                qans=muls*ans[k]%P*div%P;
            }
            else{
                if(!pmul[k]||lim[k]-pcnt[k]<0){
                    continue;
                }
                ll l=max(lim[k]-pcnt[k]-siz[k]+pssiz[k],0ll);
                ll r=c;
                if(r<l){
                    continue;
                }
                ll d1=lim[k]-pcnt[k];
                ll d2=siz[k]-pssiz[k];
				qans=(((C(d1+1,d2+r+1)-C(d1+1,d2+l))%P+P)%P)*pmul[k]%P*div%P;
            }
        }
        else{
            qans=ans2[k];
        }
        allans^=1ll*i*qans;
    }
    cout<<allans<<endl;
    ET;
}
//ETERNAL LOVE FOR Zhang Junhao, Mu Zhicheng and Zuo Hang.
//ALL FOR Zhang Junhao.