P13273

lsj2009 · 2025-07-19 20:35:59 · 题解

默认树的先序遍历是优美的。将 dfs 序改为：对于每个节点可以选择是否翻转其左右儿子（称为翻转一个节点），最终得到的树的先序遍历。dfs 序总数为 2^{2n-1} 次。

提出很强势的结论：

• 记子树 u 的权值是所有在 u 子树内出现恰好一次的颜色构成的集合。

• 我们称对于 u 子树的翻转操作是同时翻转所有 u 子树内的点，对于 dfs 序列的影响实际上就是 reverse 了一整个子树对应的区间。显然所有子树是否翻转与所有点是否翻转的方案是构成双射的，故可转为考虑前者。

• 将权值相同的子树划分进同一等价类，则翻转方案合法的充要条件是，对于所有权值大小 \ge 2 对应的等价类中，恰有偶数个子树被翻转。

证明：

• 实际上只需要说明所有 A 性质树满足条件（我们称一个树是 A 性质的，当且仅当对于任意颜色，其对应的两个节点分居根两侧）；否则找到极小的 A 性质子树，该子树必须满足其自身可以完全消去，从而可以删掉该子树归纳证明。

• 对于 A 性质树，每一等价类最多包含两棵子树（认为所有叶子都被激活，否则取出虚树再压缩掉链即可），则我们仅需要说明：

  • 大小为 1 的等价类必不可以进行翻转子树操作。

  • 大小为 2 的等价类可以同时翻转两棵子树。

  依据翻转子树实际上是 reverse 颜色序列，讨论一下是简单的。

则大小为 m 等价类对于答案贡献为 \sum\limits_{0\le i\le m,i\equiv0\pmod{2}} \binom{m}{i}=\frac{(1+1)^m+(1-1)^m}{2}=2^{m-1}，即每一等价类令答案折半；故仅需统计所有权值大小 \ge 2 对于的等价类个数 c_i，答案即为 2^{2n-1-c_i}。对于每一节点存储长为 n 的 01 串记录每个颜色是否恰好出现一次，则 c_i 即为：将所有串截取前 i 位情况下本质不同的串个数，再去除掉 popcount \le 1 的串个数，即 i+1。

逆时间轴考虑问题，先可持久化线段树合并获取所有完整的 01 串，维护哈希值（xor hash）进行排序，随 i 减小不相同的串可能变为相同：排序后 s_{k-1},s_k 串将在 i\le \operatorname{lcp}(s_{k-1},s_k) 时相同。

复杂度 \mathcal{O}(n\log^2{n})。

#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define umap unordered_map
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
template<int p>
struct mint {
    int x;
    mint() {
        x=0;
    }
    mint(int _x) {
        x=_x;
    }
    friend mint operator + (mint a,mint b) {
        return a.x+b.x>=p? a.x+b.x-p:a.x+b.x;
    }
    friend mint operator - (mint a,mint b)  {
        return a.x<b.x? a.x-b.x+p:a.x-b.x;
    }
    friend mint operator * (mint a,mint b) {
        return 1ll*a.x*b.x%p;
    }
    friend mint operator ^ (mint a,ll b) {
        mint res=1,base=a;
        while(b) {
            if(b&1)
                res*=base;
            base*=base; b>>=1;
        }
        return res;
    }
    friend mint operator ~ (mint a) {
        return a^(p-2);
    }
    friend mint operator / (mint a,mint b) {
        return a*(~b);
    }
    friend mint & operator += (mint& a,mint b) {
        return a=a+b;
    }
    friend mint & operator -= (mint& a,mint b) {
        return a=a-b;
    }
    friend mint & operator *= (mint& a,mint b) {
        return a=a*b;
    }
    friend mint & operator /= (mint& a,mint b) {
        return a=a/b;
    }
    friend mint operator ++ (mint& a) {
        return a+=1;
    }
    friend mint operator -- (mint& a) {
        return a-=1;
    }
};
const int MOD=1e9+7;
#define mint mint<MOD>
const int N=1e6+5;
const ull base=1145141;
ull pw[N];
void init(int n=1e6) {
    pw[0]=1;
    rep(i,1,n)
        pw[i]=pw[i-1]*base;
}
struct SGT {
    static const int M=2e7+5;
    struct node {
        int lson,rson;
        ull val;
    }; node tree[M];
    #define ls(k) tree[k].lson
    #define rs(k) tree[k].rson
    int p;
    int new_node() {
        return ++p;
    }
    void push_up(int k) {
        tree[k].val=tree[ls(k)].val^tree[rs(k)].val;
    }
    void update(int &k,int l,int r,int qx) {
        if(!k)
            k=new_node();
        if(l==r) {
            tree[k].val^=pw[l];
            return;
        }
        int mid=(l+r)>>1;
        if(qx<=mid)
            update(ls(k),l,mid,qx);
        else
            update(rs(k),mid+1,r,qx);
        push_up(k);
    }
    int merge(int u,int v,int l,int r) {
        if(!u||!v)
            return u|v;
        if(l==r) {
            int k=new_node();
            tree[k].val=tree[u].val^tree[v].val;
            return k;
        }
        int k=new_node(),mid=(l+r)>>1;
        ls(k)=merge(ls(u),ls(v),l,mid);
        rs(k)=merge(rs(u),rs(v),mid+1,r);
        push_up(k);
        return k;
    }
    bool cmp(int u,int v,int l,int r) {
        if(l==r)
            return tree[u].val<tree[v].val;
        int mid=(l+r)>>1;
        if(tree[ls(u)].val!=tree[ls(v)].val)
            return cmp(ls(u),ls(v),l,mid);
        else
            return cmp(rs(u),rs(v),mid+1,r);
    }
    int lcp(int u,int v,int l,int r) {
        if(l==r)
            return tree[u].val==tree[v].val? l:l-1;
        int mid=(l+r)>>1;
        if(tree[ls(u)].val!=tree[ls(v)].val)
            return lcp(ls(u),ls(v),l,mid);
        else
            return lcp(rs(u),rs(v),mid+1,r);
    }
    void print(int k,int l,int r) {
        if(l==r) {
            debug("%d",tree[k].val? 1:0);
            return;
        }
        int mid=(l+r)>>1;
        print(ls(k),l,mid);
        print(rs(k),mid+1,r);
    }
    #undef ls
    #undef rs
}; SGT T;
int ls[N],rs[N],a[N],rt[N],cnt[N],n,_;
void dfs(int u) {
    if(u>=(n<<1)) {
        T.update(rt[u],1,n,a[u]);
        return;
    }
    dfs(ls[u]);
    dfs(rs[u]);
    rt[u]=T.merge(rt[ls[u]],rt[rs[u]],1,n);
}
void solve() {
    scanf("%d%d",&_,&n);
    rep(i,1,(n<<1)-1)
        scanf("%d%d",&ls[i],&rs[i]);
    rep(i,1,n) {
        int u,v;
        scanf("%d%d",&u,&v);
        a[u]=a[v]=i;
    }
    dfs(1);
    // rep(i,1,(n<<2)-1)
    //  T.print(rt[i],1,n),debug("\n");
    sort(rt+1,rt+(n<<2),[](const int &x,const int &y) {
        return T.cmp(x,y,1,n);
    });
    // debug("-------------\n");
    // rep(i,1,(n<<2)-1)
    //  T.print(rt[i],1,n),debug("\n");
    cnt[n]=(n<<2)-1;
    rep(i,2,(n<<2)-1) {
        int x=T.lcp(rt[i-1],rt[i],1,n);
        // debug("lcp (%d,%d) = %d\n",i,i-1,x);
        --cnt[x];
    }
    per(i,n-1,1)
        cnt[i]+=cnt[i+1];
    rep(i,1,n)
        printf("%d\n",(mint(2)^((n<<1)-1-(cnt[i]-i-1))).x);
}
bool M2;
// g++ tree.cpp -std=c++14 -Wall -O2 -o tree
signed main() {
    // file_IO();
    int testcase=1;
    init();
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
    return 0;
}