Loading... ### 0x00 审题 做题先要审题，掌握对题目大体概况，准确知道要干什么。一个题分为求解限制和求解内容两部分： 1. 本题求解限制：一个经过两条非树边的简单环，这样并不好理解，需要知道这个环到底是一个什么样子的东西：显然是从第一个树出发，经过一条非树边，到第二个树，经过一条非树边，回到第一个树这样一个过程。 2. 本题求解内容：对于所有这样的环，每个环上点编号的乘积之和。这是一类计数问题，准确来说是带权计数问题：其中计的数是环，权值是环上点编号的乘积。 两个树都是完全二叉树，深度 $n$ 都小于 $18$，说明至少需要一个亚于 $\mathcal{O}\left(2^{2n}\right)$ 的算法。 ### 0x01 拆分重复子结构，合并计算 一开始一定会有一个最直接的想法，就是枚举每一个环然后计算权值，复杂度很高，无法通过。优化一个算法的方法通常是找出大量重复计算本质相同内容，拆分问题变成一些重复计算的子结构，然后把这些东西并在一起算。直接这样看似乎并不能观察出什么相同部分可以合并的，那么不妨拆分一下这个环，可以发现这个环上两个特殊的点，就是两棵树上最浅的点记为 $u,v$，从这个两个点拆开环就会变成两条链，而且这两条链都有很好性质：从 $u$ 开始，往下走，到第二个树，又一直往上走到 $v$，并且合并两条链也十分简单，把两条链的权值乘起来即可。 ### 0x02 优化第一步 那么不妨把相同的 $u,v$ 对的贡献并在一起算，只要确定了一对 $u,v$ 然后选出两条链即可，这样就把环的问题转化成了链，但是并不是任意两条链都可以，需要满足两条链不交才行。为了解决不交的限制，继续观察一些性质，两个树上看似乎很困难，那么就先简化问题变成如何在一棵树上选出同一起点两条不交的链。由于是二叉树这个问题很简单，只需要考虑 $u$ 从到左儿子出去往下一条链、从右儿子出去一条链即可。现在把两个树拼起来看，可以发现若两个树 $u,v$ 都是左儿子出去一条、右儿子出去一条，那么四条链拼起来一定也是不交的。这样就得到了一个 $\mathcal{O}\left(n2^{2n}\right)$ 的算法： 1. 枚举两个树上的两个端点 $u,v$ 2. 计算从 $u$ 从左右儿子出发，到第二个树上每个点时的权值 3. 在 $v$ 处分类讨论，$v$ 的左右儿子分别对应是从 $u$ 左儿子还是右儿子出发，然后乘起来即可。 ### 0x03 优化第二步 目前还是无法通过，瓶颈在于要枚举两个端点，继续沿用刚才的思路，拆分重复子结构，合并计算。可以发现其实对于一个 $u$，重复计算了很多次他到第二个树的权值，那么可不可以合并起来计算呢，答案是可以的。只需要计算一次从第一个树出发，到第二个树每个点的权值。但是似乎没什么用，还是无法通过。 还个思路，优化算法的第二种思路是去掉不必要的计算，发现对于一个 $u$ 很多个在第二个树上选出的 $v$ 的贡献都是 $0$，也就是根本不会存在这样的环，考虑把 $v$ 枚举的范围缩小。由于要形成环至少需要有一条链，所以得到了 $v$ 范围的一个必要条件就是，一定在 $u$ 出发的某条链上，这个范围有多大呢可以分析一下，假设 $u$ 在第一个树上子树大小是 $size_u$，那么其叶子只有 $\lceil\frac{size_u}{2}\rceil$ 个，每个叶子跳到第二个树上有只有 $n$ 个祖先，所以最多只有 $\mathcal{O}\left(nsize_u\right)$ 点可能成为 $v$。整体分析一下： $$ \sum_{i=1}^{2^n-1} nsize_i=n\sum_{i=1}^{2^n-1} size_i $$ 对于后面的部分，换种方法分析一下，对于每个点最多只有 $n$ 个祖先，所以这个点在复杂度只会贡献 $n$ 次，所以后面部分是 $\mathcal{O}\left(n2^{n}\right)$ 的，总体复杂度就是 $\mathcal{O}\left(n^22^{n}\right)$ 的，可以通过。 ### 0x04 代码实现 分两次跑 dfs，表示是从 $u$ 的左儿子还是右儿子出发的，第一次把权值记下来，第二次直接统计答案即可。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} const long long mod=1000'000'007; int n,ar[1<<19]; long long dp[1<<19],res; void dfs2(int p,long long now,char op){ while(p!=1){ (now*=p)%=mod; if(op) (dp[p]+=now)%=mod; else (res+=now*dp[p^1]%mod*(p>>1))%=mod; p>>=1; } return; } void dfs1(int p,long long now,char op){ (now*=p)%=mod; if(p>=(1<<(n-1))) return dfs2(ar[p],now,op); return dfs1(p<<1,now,op),dfs1(p<<1|1,now,op); } void clear2(int p){ while(p!=1) dp[p]=0,p>>=1; return; } void clear1(int p){ if(p>=(1<<(n-1))) return clear2(ar[p]); return clear1(p<<1),clear1(p<<1|1); } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i; n=read(); for(i=0;i<(1<<(n-1));++i) ar[i+(1<<(n-1))]=read()+(1<<(n-1))-1; for(i=1;i<(1<<(n-1));++i){ dfs1(i<<1,i,1); dfs1(i<<1|1,1,0); clear1(i); } print(res); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` ### 0x05 总结 做本题过程中主要用到的优化思路有： 1. 拆分大问题为相似的子结构。 2. 找出重复的子结构合并计算。 3. 找出不必要的计算量，缩小计算范围。 做题要结合多种思维方式，跳脱出当前的思维困局，善用多种技巧，才能解题。 最后修改：2024 年 05 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用，使用点这里使用虚拟货币进行赞赏