专栏文章

P13273

llsj2009Isj2OO9
P13273题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miou2hzh
此快照首次捕获于
2025/12/03 01:09
3 个月前
此快照最后确认于
2025/12/03 01:09
3 个月前
查看原文
默认树的先序遍历是优美的。将 dfs 序改为：对于每个节点可以选择是否翻转其左右儿子（称为翻转一个节点），最终得到的树的先序遍历。dfs 序总数为 22n−12^{2n-1} 次。
提出很强势的结论：
  • 记子树 uu 的权值是所有在 uu 子树内出现恰好一次的颜色构成的集合。
  • 我们称对于 uu 子树的翻转操作是同时翻转所有 uu 子树内的点，对于 dfs 序列的影响实际上就是 reverse 了一整个子树对应的区间。显然所有子树是否翻转与所有点是否翻转的方案是构成双射的，故可转为考虑前者。
  • 将权值相同的子树划分进同一等价类，则翻转方案合法的充要条件是，对于所有权值大小 ≥2\ge 2 对应的等价类中，恰有偶数个子树被翻转。
证明：
  • 实际上只需要说明所有 A 性质树满足条件（我们称一个树是 A 性质的，当且仅当对于任意颜色，其对应的两个节点分居根两侧）；否则找到极小的 A 性质子树，该子树必须满足其自身可以完全消去，从而可以删掉该子树归纳证明。
  • 对于 A 性质树，每一等价类最多包含两棵子树（认为所有叶子都被激活，否则取出虚树再压缩掉链即可），则我们仅需要说明：
    • 大小为 11 的等价类必不可以进行翻转子树操作。
    • 大小为 22 的等价类可以同时翻转两棵子树。
    依据翻转子树实际上是 reverse 颜色序列，讨论一下是简单的。
则大小为 mm 等价类对于答案贡献为 ∑0≤i≤m,i≡0(mod2)(mi)=(1+1)m+(1−1)m2=2m−1\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}，即每一等价类令答案折半；故仅需统计所有权值大小 ≥2\ge 2 对于的等价类个数 cic_i，答案即为 22n−1−ci2^{2n-1-c_i}。对于每一节点存储长为 nn 的 0101 串记录每个颜色是否恰好出现一次，则 cic_i 即为：将所有串截取前 ii 位情况下本质不同的串个数，再去除掉 popcount ≤1\le 1 的串个数，即 i+1i+1。
逆时间轴考虑问题，先可持久化线段树合并获取所有完整的 0101 串，维护哈希值（xor hash）进行排序，随 ii 减小不相同的串可能变为相同：排序后 sk−1,sks_{k-1},s_k 串将在 i≤lcp⁡(sk−1,sk)i\le \operatorname{lcp}(s_{k-1},s_k) 时相同。
复杂度 O(nlog⁡2n)\mathcal{O}(n\log^2{n})。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...