资讯详情

题目保证存在一种合法方案，我们可以考虑由一个合法方案怎么调整出不同的合法方案。

为了方便理解，我们钦定优先向左遍历，把换向操作转换成翻转子树的操作。

容易发现，翻转一棵子树时已经合法匹配的点不受影响，那么只有那些当前未配对的点需要考虑。跟虚树的角度差不多，我们把这些子树内已经匹配上的点踢掉分析。

分析问题的重要方法：从小入手。

两种颜色

\(X\) 和 \(Y\) 子树内都有一个 \(A\) 和一个 \(B\) 颜色节点没有参与匹配，翻转点 \(X\) 后应该翻转 \(Y\) 才能构成新的合法结构。

\(Y\) 子树内只有 \(A_1\) 没有匹配，可以随意翻转；而 \(X\) 翻转后无法通过翻转其他节点构成合法结构。

可以发现，对于一个合法序列，翻转一部分，如果这个部分中至少有两个未匹配的点，那么必须将对应区间也翻转，或者在其他点把这个部分翻转回来。

那假如我们已经翻转了一个部分，到底翻转哪些点才能转回合法？

两个不够具有普适性，我们引入第三个节点。

三种颜色

翻转 \(Y\) 后，\(Z\) 和 \(W\) 都可以把 \(A_2,B_2\) 相对位置调整正确，然而这会使得 \(C_2\) 调到中间不再合法，因此只能翻转 \(W\)。

通过上述的分析，我们发现，翻转了一个点 \(u\)，就必须翻转树上管辖着一模一样的 \(S\) 的 \(v\)​。

至此我们可以得出结论：设 \(S_u\) 为 \(u\) 子树内未匹配节点集合。若 \(|S_u| \geq 2\)，则当且仅当 \(S_u=S_v \ (u \neq v)\)，可以通过同时翻转子树 \(u, v\) 得出新的合法方案。若 \(|S_u|=1\)，那怎么样翻转都行。

怎么计数？设等价类 \(A_k\) 包含了所有 \(S\) 相同，且 \(|S| \geq 2\) 的点，等价类共有 \(m\) 个。设 \(|S|=1\) 的点有 \(t\) 个。每个等价类我们都可以任选偶数个翻转，则：

\[ans=2^t\prod_{k=1}^{m}\sum_{i=0}^{|A_k|/2} \binom{|A_k|}{2i}=2^t\prod_{k=1}^{m}2^{|A_k|-1}=2^{2n-1-m} \]

问题转化为计算等价类的个数。

第 \(i\) 次操作加入颜色 \(i\)，下标不仅是元素编号，也表示了时间，务必记住这一点。

用 01 序列表示集合 \(S_u\)。若两 01 序列的 lcp 长度为 \(l\)，则说明在前 \(l\) 次操作里它们都属于同一个等价类！

使用树上差分标记修改，显然可以用线段树高效维护合并集合。至此我们得到了每个点子树内的未匹配点集，我们把这些字符串记为 \(a[i]\)。

已知所有集合，如何计数等价类？

对所有字符串按字典序排序后（比较操作就是查询 lcp，这可以通过对比两棵线段树上区间哈希值来实现，单次对比复杂度是 \(O(\log n)\) 的），若 \(\text{lcp}(a[i-1], a[i])=L\)，这意味着在 \(L+1\) 时新出现了一个等价类。

由于更长的 lcp 覆盖了短的 lcp，如果字符串 \(\text{lcp}(a[i], a[j]) \leq \text{lcp}(a[i], a[i-1])\)，那么在 \(i-1\) 或更早，\(a[i], a[j]\)​​ 分歧产生的新等价类已经被计数过了。所以这就覆盖了所有的情况，避免了冗余的比较。

Code

有点难写啊，空间有点玄学，瞎开的。

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN = 2e6;
const int MAXB = 24;
int c, n;
int lc[MAXN], rc[MAXN];
int fa[25][MAXN], depth[MAXN], pw131[MAXN], ans[MAXN];
vector<int> add[MAXN], del[MAXN];
struct Mergeable_Segment_Tree {struct Node {int h, pos1, pos2;int lc, rc;Node() {h = lc = rc = 0;pos1 = pos2 = 1e9;}};Node tr[int(2e7)];int root[MAXN], tot;void push_up(int p, int l, int r) {int mid = (l + r) >> 1;tr[p].h = (tr[tr[p].lc].h * pw131[r - mid] + tr[tr[p].rc].h) % MOD;if (tr[tr[p].lc].pos1 == 1e9) {tr[p].pos1 = tr[tr[p].rc].pos1;tr[p].pos2 = tr[tr[p].rc].pos2;} else {tr[p].pos1 = tr[tr[p].lc].pos1;if (tr[tr[p].lc].pos2 != 1e9) tr[p].pos2 = tr[tr[p].lc].pos2;else tr[p].pos2 = tr[tr[p].rc].pos1;}}int update(int p, int l, int r, int pos, int k) {int q = ++tot;tr[q] = tr[p];if (l == r) {tr[q].h = k;tr[q].pos1 = (k ? l : 1e9);tr[q].pos2 = 1e9;return q;}int mid = (l + r) >> 1;if (pos <= mid) tr[q].lc = update(tr[p].lc, l, mid, pos, k);else tr[q].rc = update(tr[p].rc, mid + 1, r, pos, k);push_up(q, l, r);return q;}int merge(int p1, int p2, int l, int r) {if (!p1 || !p2) return p1 ? p1 : p2;int p = ++tot;if (l == r) {tr[p].h = (tr[p1].h + tr[p2].h) % MOD;tr[p].pos1 = min(tr[p1].pos1, tr[p2].pos1);tr[p].pos2 = 1e9;return p;}int mid = (l + r) >> 1;tr[p].lc = merge(tr[p1].lc, tr[p2].lc, l, mid);tr[p].rc = merge(tr[p1].rc, tr[p2].rc, mid + 1, r);push_up(p, l, r);return p;}pair<int, int> lcp(int p1, int p2, int l, int r) {if (tr[p1].h == tr[p2].h) return make_pair(n + 1, 1);if (!p1) return make_pair(tr[p2].pos1, 2);if (!p2) return make_pair(tr[p1].pos1, 1);if (l == r) return make_pair(l, !tr[p1].h ? 2 : 1);int mid = (l + r) >> 1;if (tr[tr[p1].lc].h != tr[tr[p2].lc].h) return lcp(tr[p1].lc, tr[p2].lc, l, mid);else return lcp(tr[p1].rc, tr[p2].rc, mid + 1, r);}
};
Mergeable_Segment_Tree mst;
void dfs(int x) {if (!x) return;for (int i = 1; i <= MAXB; ++i) {fa[i][x] = fa[i - 1][fa[i - 1][x]];}if (lc[x]) {fa[0][lc[x]] = x;depth[lc[x]] = depth[x] + 1;dfs(lc[x]);}if (rc[x]) {fa[0][rc[x]] = x;depth[rc[x]] = depth[x] + 1;dfs(rc[x]);}
}
inline int lca(int x, int y) {if (depth[x] != depth[y]) {if (depth[x] < depth[y]) {swap(x, y);}for (int i = MAXB; i >= 0; --i) {if (depth[fa[i][x]] >= depth[y]) {x = fa[i][x];}}}if (x == y) return x;for (int i = MAXB; i >= 0; --i) {if (fa[i][x] != fa[i][y]) {x = fa[i][x];y = fa[i][y];}}return fa[0][x];
}
void dfs2(int x) {if (!x) return;dfs2(lc[x]);dfs2(rc[x]);mst.root[x] = mst.merge(mst.root[x], mst.root[lc[x]], 1, n);mst.root[x] = mst.merge(mst.root[x], mst.root[rc[x]], 1, n);for (int d : del[x]) {mst.root[x] = mst.update(mst.root[x], 1, n, d, 0);}for (int d : add[x]) {mst.root[x] = mst.update(mst.root[x], 1, n, d, 1);}
}
bool cmp(int p1, int p2) {return mst.lcp(p1, p2, 1, n).second == 2;
}
inline int qpow(int a, int b) {int res = 1;while (b) {if (b & 1) res = (res * a) % MOD;a = (a * a) % MOD;b >>= 1;}return res;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> c >> n;depth[1] = 1;pw131[0] = 1;for (int i = 1; i <= n; ++i) {pw131[i] = (pw131[i - 1] * 131) % MOD;}for (int i = 1; i <= 2 * n - 1; ++i) {cin >> lc[i] >> rc[i];}dfs(1);for (int i = 1; i <= n; ++i) {int a, b;cin >> a >> b;int l = lca(a, b);add[a].emplace_back(i);add[b].emplace_back(i);del[l].emplace_back(i);}dfs2(1);sort(mst.root + 1, mst.root + 2 * n, cmp);for (int i = 1; i <= 2 * n - 1; ++i) {if (mst.tr[mst.root[i]].pos2 != 1e9) { //新等价类对应S集合的元素个数必须大于1if (i == 1) ++ans[mst.tr[mst.root[1]].pos2];else++ans[max(mst.lcp(mst.root[i], mst.root[i - 1], 1, n).first, mst.tr[mst.root[i]].pos2)];}}for (int i = 1; i <= n; ++i) {ans[i] += ans[i - 1];cout << qpow(2, 2 * n - 1 - ans[i]) << endl;}return 0;
}