Wuyanru's blog
0%

[QOJ7509] 01tree

发表于 分类于 ，

打开别人的代码，发现一车野生的组合数。

打开官方题解，发现一个式子都没有，我请问呢？

题目链接。

题意

现在有一棵树，每一个点上有一个数字 或 。

现在可以进行任意多次操作，每一次操作为选择两个相邻的点，满足这两个点上数字相同，然后将这两个点的数字都 flip 一下。

给定一个起始状态和一个终止状态，但有一些位置不确定。

对于每一种可能的起始状态与终止状态，计算最小的操作次数之和，不存在方案记作需要 次操作。

。

题解

首先考虑怎么计算某一个固定方案的最小次数。

感觉是一个简单 trick，见过就不难，比如这个题。

做法是把所有深度为奇数的点上的数字 flip，这样交换两个相同的数字就变成交换两个不同的数字。

所以我们现在的题意是，每一次可以交换两个相邻位置上的数字，问最小操作几次。

显然，如果起始状态与终止状态中 的个数不同，显然无解。

否则对于每一条边考虑，显然这条边上的操作次数，至少是起始状态与终止状态中，子树内 的数量的差。

而显然我们能对每一条边都卡到下界，贪心在每一个点合并即可。

现在考虑原问题，还是拆贡献，我们分别对每一条边计算所有方案中这条边交换的次数和。

下文中，我们将起始状态称为树 ，终止状态称为树 。现在考虑一条边 ，其中 为父亲。

最暴力的想法，大概是我们需要枚举 在两棵树内部分别有几个未知点选择了 。

由于需要满足两棵树上 的数量相等，所以我们还得枚举 子树外部的未知点选择情况。

这样总复杂度就变成 的了，过你吗。

考虑设 中 子树内操作之后有 个点从未知变成 ，子树外有 个点从未知变成 ，整棵树初始有 个 ，子树内初始有 个 。

同理设 中 子树内操作之后有 个点从未知变成 ，子树外有 个点从未知变成 ，整棵树初始有 个 ，子树内初始有 个 。

我们要求左右两侧 的数量相等，这相当于左边 的数量加上右边 的数量恰好为 。

列出式子，，相当于 。

设子树大小为 ，则这条边交换次数为 。

由于 都是定值，考虑枚举 的值，那么我们就知道 的值了。

设 的 子树内部共有 个未知点，两棵树共有 个未知点，则此时方案数为 。

也就是说，这里的贡献大概是一个 的形式，并且对于所有边的 均为定值。

复杂度为 ，现在我们需要快速求出这一车式子的值。

由于变量只有 ，考虑莫队，现在问题在于 变化 之后，这个式子的值会怎么变。

考虑一个稍微简单一点的问题，考虑怎么维护 的值。

当 变化的时候，这个式子是会多一项／少一项，这是好维护的。

当 变化的时候，考虑这个式子的组合意义。

不难发现，这个式子的值相当于，现在有 个位置，你需要给 个位置填上 ，剩余位置填 ，额外要求前 个位置最多只能有 个 。

增加 ，那么现在前 个位置只能有 个 ，相比于原来，少了前 个位置恰好有 个 并且第 个位置也有一个 的方案。

所以只需要直接给方案数减去 。 变小的时候就是加上一些方案。

现在回到原问题，考虑怎么维护 的值。

先考虑 增大 的时候，这个式子的值会发生怎样的变化。

直接分 和 考虑，不难发现 的部分增加了 ，而 的部分减少了 。

而这两部分我们都会维护（tips：），所以我们直接算一下就好了！

在考虑 增大的时候怎么维护，还是一样考虑组合意义。

这个式子的含义是，现在有 个位置，你需要给 个位置填 ，剩余位置填 ；若一个方案前 个位置有 个 ，则贡献为 ，求总贡献。

现在 变大了 ，显然只有 那个位置填了 的方案，贡献会产生变化。

不难发现，答案会变化 。

那么我们再额外维护一个 就好了，这实在是太你妈难推了！

这样我们直接就能得到一个 的做法，但是这个做法还能优化。

考虑实际我们询问的 取值和子树内信息是有关的，所以我们每一个点在计算的时候，直接从重儿子转移过来。

对于每一个点，转移复杂度是所有轻儿子 siz 和的，所以复杂度是 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
template<const int N,const int M>
struct graph
{
    int head[N+5];
    int ww[M+5];
    int t[M+5];
    int x[M+5];
    int cntm;
    graph(){ cntm=1;}
    inline void clear(int n=N)
    {
        cntm=1;
        for(int i=1;i<=n;i++) head[i]=0;
    }
    inline void ad(int u,int v,int w=0)
    {
        cntm++;
        t[cntm]=v;
        x[cntm]=head[u];
        ww[cntm]=w;
        head[u]=cntm;
    }
    inline void add(int u,int v,int w=0)
    {
        ad(u,v,w);
        ad(v,u,w);
    }
    inline int st(int num){ return head[num];}
    inline int to(int num){ return t[num];}
    inline int nx(int num){ return x[num];}
    inline int w(int num){ return ww[num];}
};
graph<100000,200000>g;
const int mod=1'000'000'007;
int hson[100005];
int siz[100005];
char s[100005];
char t[100005];
int s1[100005];
int t1[100005];
int sw[100005];
int tw[100005];
int A[100005];
int D[100005];
ll jc[200005];
ll inv[200005];
ll F[100005];
ll G[100005];
ll H[100005];
int n,b,c;ll ans;
inline ll qow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void dfs1(int num,int fa,int dep)
{
    siz[num]=1,hson[num]=0;
    sw[num]=(s[num]=='?')?1:0;
    tw[num]=(t[num]=='?')?1:0;
    s1[num]=(s[num]=='0'+dep)?1:0;
    t1[num]=(t[num]=='0'+dep)?1:0;

    for(int i=g.st(num);i;i=g.nx(i))
    {
        int p=g.to(i);
        if(p==fa) continue;
        dfs1(p,num,dep^1);
        siz[num]+=siz[p];
        sw[num]+=sw[p];
        tw[num]+=tw[p];
        s1[num]+=s1[p];
        t1[num]+=t1[p];
        if(siz[p]>siz[hson[num]]) hson[num]=p;
    }
}
inline ll C(int a,int b)
{
    if(a<b||b<0) return 0;
    return jc[a]*inv[b]%mod*inv[a-b]%mod;
}
void dfs2(int num,int fa)
{
    A[num]=sw[num]+tw[num];
    D[num]=sw[num]+s1[num]-t1[num];

    for(int i=g.st(num);i;i=g.nx(i))
    {
        int p=g.to(i);
        if(p==fa) continue;
        dfs2(p,num);
    }

    // printf("num=%d : %d %d %d %d\n",num,A[num],b,c,D[num]);
    int a,d;ll f,g,h;
    if(!hson[num]) a=d=0,f=0,g=C(b,c),h=0;
    else
    {
        int p=hson[num];
        a=A[p],d=D[p];
        f=F[p],g=G[p],h=H[p];
    }
    // printf("%d %d %d %d : %lld %lld %lld\n",a,b,c,d,(f%mod+mod)%mod,(g%mod+mod)%mod,(h%mod+mod)%mod);

    while(d<D[num])
    {
        f=(f+2*g-C(b,c))%mod;
        h=(h+C(a,d)*C(b-a-1,c-d-1))%mod;
        d++;
        g=(g+C(a,d)*C(b-a,c-d))%mod;
    }
    while(d>D[num])
    {
        g=(g-C(a,d)*C(b-a,c-d))%mod;
        d--;
        h=(h-C(a,d)*C(b-a-1,c-d-1))%mod;
        f=(f-2*g+C(b,c))%mod;
    }
    // printf("%d %d %d %d : %lld %lld %lld\n",a,b,c,d,(f%mod+mod)%mod,(g%mod+mod)%mod,(h%mod+mod)%mod);
    while(a<A[num])
    {
        f=(f+C(b-1,c-1)-2*h)%mod;
        g=(g-C(a,d)*C(b-a-1,c-d-1))%mod;
        h=(h-C(a,d-1)*C(b-a-2,c-d-1))%mod;
        a++;
    }
    while(a>A[num])
    {
        a--;
        h=(h+C(a,d-1)*C(b-a-2,c-d-1))%mod;
        g=(g+C(a,d)*C(b-a-1,c-d-1))%mod;
        f=(f-C(b-1,c-1)-2*h)%mod;
    }
    (ans+=f)%=mod;
    F[num]=f,G[num]=g,H[num]=h;
    // printf("%lld %lld %lld\n",(f%mod+mod)%mod,(g%mod+mod)%mod,(h%mod+mod)%mod);
}
inline void solve()
{
    g.clear(n),n=read();ans=0;
    for(int i=1;i<n;i++) g.add(read(),read());
    scanf("%s%s",s+1,t+1);

    jc[0]=inv[0]=1;
    for(int i=1;i<=2*n;i++)
    {
        jc[i]=jc[i-1]*i%mod;
        inv[i]=qow(jc[i],mod-2);
    }

    dfs1(1,1,0);
    b=sw[1]+tw[1];
    c=sw[1]+s1[1]-t1[1];
    dfs2(1,1);

    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}