https://codeforces.com/gym/102452/problem/G
很容易我们能想到乘法怎么做，但是光有乘法是求不出K的，必然要有加法。 比如1-2-3，1-4-5，5个节点的树，如果节点2，3的值一样，4，5的值一样，那么就有2*2种方案，而节点1的值可以确定是否还能+1。因此加法得从这里进行突破。 考虑到最熟悉的树是二叉树，可以将答案划分为两个子树，假设当前要计算的数为k，若k为偶数，则分为2，和k/2，当前节点的值为两个子树最优解的值+1；若k为奇数，则同样分为2和k/2，当前节点的值和两个子树的最优解的值相同。注意一定是要最优解的值，因为当前根节点的值可能不等于两个子树的最优解值的和，那么返回后，也就是回到父亲节点，如果直接用修改的节点的值计算是不能得到最优解的。
注意：K=1时第二行不能空着。
#include<cstdio> using namespace std; const int maxn = 1e5 + 5; int K, fa[maxn], cnt = 1, val[maxn]; int dfs(int f, int n) { int nxtf = (++cnt); fa[nxtf] = f; if (n == 1)return val[nxtf] = 1; cnt++; fa[cnt] = nxtf; val[cnt] = 1; if (n == 2)return val[nxtf] = 1; cnt++; fa[cnt] = cnt - 1; val[cnt] = 1; int res = dfs(nxtf, n / 2); if (n & 1) { val[nxtf] = res + 1; return res + 1; } else { val[nxtf] = res + 2; return res + 1; } } int main(void) { scanf("%d", &K); if (K <= 2) { if (K == 1)printf("2\n1\n2 1\n"); if (K == 2)printf("2\n1\n1 1\n"); } else { cnt++; fa[cnt] = 1; val[cnt] = 1; cnt++; fa[cnt] = cnt - 1; val[cnt] = 1; int res = dfs(1, K / 2); if (K & 1)val[1] = res + 1; else val[1] = res + 2; printf("%d\n", cnt); for (int i = 2; i <= cnt; i++)printf("%d%c", fa[i], i == cnt ? '\n' : ' '); for (int i = 1; i <= cnt; i++)printf("%d%c", val[i], i == cnt ? '\n' : ' '); } return 0; }