Cat Virus

题目大意

一棵树，节点有黑色和白色，黑色节点的所有子节点都为黑色
一棵树有$K(2<=k<=2·10^{18})$种染色方式，构造这棵树。

Time : 2000 ms
Memory: 262144 kB

解题思路及分析

一开始把题干里的ways翻译成道路懵了半天
可以先找K是怎么算的，给一棵树知道怎么求K，再反过来想应该会容易些
既然是树，理论上会有与子树之间的递归的关系
稍微画画图可以发现，一棵树的K值等于所有子树K值的乘积+1
理解起来也不算难理解，染成黑色的点子节点都是黑色，所以一个节点的染色是会影响它的子树，但是两棵子树之间是互不影响的，所以先考虑根节点为白色的情况，这里采用的是所有子树K值的乘积；当根节点为黑色，只有一种情况，所以
然后找递归出口，显然1个节点的情况有2种染色方式，非黑即白；空树的染色方式可以被认为是1
求K的方法如上，然后就可以反过来构造树了
构造每一层时将K减一并进行分解
这里为了方便每次减一除二，如果能整除2就一直除下去，在该层一直添加单个节点
无法整除之后进入下一层，继续减一除二
理论时间复杂度$O(log_2 n)$

AC代码

#include <bits/stdc++.h>
typedef long long llong;
const int N = 1e5 + 5;
using namespace std;
vector<int> a[N];	// 存储子节点，类似邻接表
 
// 最开始不知道怎么构造，就先写了一个求K的代码
// int getK(vector<int> t) {
//     int res = 1;
//     for (int i = 0; i < t.size(); i++) {
//         res *= getK(a[t[i]]);
//     }
//     return res + 1;
// }

int n = 1;
void to(int i, llong k) {
    llong tmp = k - 1;
    while (tmp % 2 == 0) {
        tmp /= 2;
        a[i].push_back(++n);	//能整除则一直在本层添加节点
    }
    if (tmp == 1)    return;	// 空树K为1，此时说明构造结束
    a[i].push_back(++n);		// 无法整除则继续在本层添加一个节点，并在这棵树的基础上添加
    to(n, tmp);	
}
 
int main()
{
    llong k;
    cin >> k;
    to(1, k);
    printf("%d\n", n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < a[i].size(); j++) {
            printf("%d %d\n", i, a[i][j]);
        }
    }
    return 0;
}