这题挺恶心的。

首先一颗树的时候点分加卷积统计答案，注意合并子树时按深度从小到大合并，否则复杂度就爆了。

我偷懒用size从小到大合并，复杂度应该还是两个log.

然后考虑万恶的环。

先随便删掉环上一条边，按照树统计一下答案。

然后考虑

必须经过环上该条边的答案但又不经过整个环的答案。

考虑再钦定一条边不经过，算答案。

然后递归做就行了。

最后加上经过整个环的答案。

时间复杂度\(O(n log^2(n))\)

// luogu-judger-enable-o2// luogu-judger-enable-o2#include 
    
     using namespace std;typedef vector
     
       poly;typedef long long ll;poly a,b;const int P=1<<17;const int M=998244353;const int G=3; int rev[P],w[P];namespace{    int add(int x,int y){        return (x+=y)>=M?x-M:x;    }    int sub(int x,int y){        return (x-=y)<0?x+M:x;    }    int mul(int x,int y){        return (ll)x*y%M;    }    int fp(int x,int y){        int ret=1;        for (; y; y>>=1,x=mul(x,x))            if (y&1) ret=mul(ret,x);        return ret;    }}int inv2[30];void init(int len){    for (int i=1; i
      
       1) w[i+1]=fp(G,(M-1)/(i<<1));        for (int j=2; j
       
        >31)&M;                ++b;                (*l)+=y-M;                (*l)+=((*l)>>31)&M;                ++l;            }        }     }} void INTT(int *a,int len,int bit){    reverse(a+1,a+len);    NTT(a,len);    int ni=inv2[bit];    for (int i=0; i
        
         >1]>>1|((i&1)?len>>1:0);    NTT(a.data(),len);    NTT(b.data(),len);    for (int i=0; i