Description：
给你一棵\(n\)个节点的树，要求你将结点填入一个两行无穷列的网格中，要求点1 在左上角，有边相连的结点在相邻的格子中，求方案数模\(10^9+7\)。
\(1\leq n\leq 300000\)
Example:
| input | output |
| 5 1 2 2 3 2 4 4 5 | 4 |
Solution：
太神了！
\(dp[i]\)表示只剩\(i\)的子树没有填，\(i\)放在左上角，且\(i\)左侧的格子不能再填入，的方案数。
然后我是看这篇博客才看懂的 Orz
然而我最后还是只写了个\(n log(n)\)的，不知道 jump(x, y)怎么优化了。
然后写完还调了好久，都是一些傻逼错误，什么if里&&写成==啊，倍增数组忘记初始化啊，边界情况没判啊。。。
具体细节看代码。
Code：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
#include <cstdio> #include <algorithm> #define FOR(a,b,c) for(int a=b;a<=c;a++) #define FORD(a,b,c) for(int a=b;a>=c;a--) #define mo 1000000007 using namespace std; int tot, F[300010], N[600010], V[600010]; void addedge(int x, int y) { V[++tot] = y; N[tot] = F[x]; F[x] = tot; } int n, x, y; int g[300010][20]; int jump(int x, int y) { FORD(i, 19, 0) if ((y >> i) & 1) x = g[x][i]; return x; } int son[300010][2], is_chain[300010], chain_len[300010], chain_end[300010], dep[300010]; void dfs(int x, int fa) { dep[x] = dep[fa] + 1; g[fa][0] = x; for (int now = F[x]; now; now = N[now]) if (V[now] != fa) { if (son[x][1]) { puts("0"); exit(0); } if (son[x][0]) son[x][1] = V[now]; else son[x][0] = V[now]; dfs(V[now], x); } if (!son[x][0]) { is_chain[x] = chain_len[x] = 1; } else if (!son[x][1]) { if (is_chain[son[x][0]]) { is_chain[x] = 1; chain_len[x] = chain_len[son[x][0]] + 1; } else chain_end[x] = chain_end[son[x][0]]; } else { chain_end[x] = x; } } int f[300010]; int bl[300010]; int dp(int x); int battle(int v, int t) { int ret = 0; if (is_chain[v] && is_chain[t] && chain_len[v] == chain_len[t]) ret++; if (is_chain[v]) { if ((is_chain[t] && chain_len[t] > chain_len[v]) || (!is_chain[t] && dep[chain_end[t]] - dep[t] >= chain_len[v])) { int w = jump(t, chain_len[v]); ret += dp(w); if (ret >= mo) ret -= mo; } } if (is_chain[t]) { if ((is_chain[v] && chain_len[v] > chain_len[t]) || (!is_chain[v] && dep[chain_end[v]] - dep[v] >= chain_len[t])) { int w = jump(v, chain_len[t]); ret += dp(w); if (ret >= mo) ret -= mo; } } return ret; } int dp(int x) { if (bl[x]) return f[x]; bl[x] = 1; f[x] = 0; if (!son[x][0]) return f[x] = 1; // x没有孩子 if (!son[x][1]) { // x有1个孩子y int y = son[x][0]; // y放x下方 if (!son[y][0]) f[x]++; // y没有孩子 else if (!son[y][1]) { // y有一个孩子z int z = son[y][0]; f[x] += dp(z); if (f[x] >= mo) f[x] -= mo; } // y放x右边 f[x] += dp(y); if (f[x] >= mo) f[x] -= mo; if (is_chain[y]) { if ((chain_len[y] & 1) && chain_len[y] > 1) f[x]++; if (f[x] >= mo) f[x] -= mo; } else { int z = chain_end[y]; int u = son[z][0], v = son[z][1]; int dlt_len = dep[z] - dep[x] + 1; if (is_chain[u] && (dlt_len == chain_len[u] || dlt_len == chain_len[u] + 2)) f[x] += dp(v); if (f[x] >= mo) f[x] -= mo; if (is_chain[v] && (dlt_len == chain_len[v] || dlt_len == chain_len[v] + 2)) f[x] += dp(u); if (f[x] >= mo) f[x] -= mo; if (son[u][1]) { int s = son[u][0], t = son[u][1]; if (is_chain[s] && chain_len[s] == dlt_len - 1) f[x] += battle(v, t); if (f[x] >= mo) f[x] -= mo; if (is_chain[t] && chain_len[t] == dlt_len - 1) f[x] += battle(v, s); if (f[x] >= mo) f[x] -= mo; } if (son[v][1]) { int s = son[v][0], t = son[v][1]; if (is_chain[s] && chain_len[s] == dlt_len - 1) f[x] += battle(u, t); if (f[x] >= mo) f[x] -= mo; if (is_chain[t] && chain_len[t] == dlt_len - 1) f[x] += battle(u, s); if (f[x] >= mo) f[x] -= mo; } } } else { // x有2个孩子 y, z int y = son[x][0], z = son[x][1]; // y右 z下 if (!son[z][0]) f[x] += dp(y); if (f[x] >= mo) f[x] -= mo; if (!son[z][1] && son[z][0]) f[x] += battle(y, son[z][0]); if (f[x] >= mo) f[x] -= mo; // z右 y下 if (!son[y][0]) f[x] += dp(z); if (f[x] >= mo) f[x] -= mo; if (!son[y][1] && son[y][0]) f[x] += battle(z, son[y][0]); if (f[x] >= mo) f[x] -= mo; } return f[x]; } int main() { scanf("%d", &n); FOR(i, 1, n - 1) { scanf("%d%d", &x, &y); addedge(x, y); addedge(y, x); } dfs(1, 0); FOR(i, 1, 19) FOR(j, 1, n) g[j][i] = g[g[j][i - 1]][i - 1]; printf("%d\n", dp(1)); return 0; } |