Delicacy
Solution
暴力 DP：(f_{i,u}) 表示 (i) 时刻到达 (u) 的最大收益，注意到转移 (f_{i,v}leftarrow f_{i-w,u})（(wle 5)）对所有的 (i) 都一样，可以使用矩阵快速幂，矩阵规模为 (nw)。
对于原问题，设 (g_{i,u}) 表示从小到大第 (i) 个时间点到达 (u) 的最大收益，这里从 (i) 从小到大，不断让 (g) 乘上转移矩阵 (A) 的 (t_i-t_{i-1}) 次幂之后再加上 (x_i) 的额外收益 (y_i)。
对于求一个 (1 imes n) 行向量 (F) 和一个 (n imes n) 矩阵 (A) 的 (t) 次幂的乘积，我们有 (O(n^3log t)) 预处理，每组询问 (O(n^2log t)) 的做法：预处理 (A^{2^0})，(A^{2^1})，(A^{2^2})，(dots)，每次询问把 (t) 二进制分解，依次把对应的 (A^{2^i}) 乘在 (F) 右边，每次相乘只做了一个 (1 imes n) 和 (n imes n) 的矩阵乘法。
总复杂度 (O((k+nw)(nw)^2log t))。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}
typedef long long ll;
const int N = 55, E = 255;
int n, m, T, k, c[N];
struct matrix
{
int n, m; ll a[E][E];
matrix() {}
matrix(int _n, int _m) :
n(_n), m(_m) {memset(a, -1, sizeof(a));}
friend inline matrix operator * (matrix a, matrix b)
{
matrix res = matrix(a.n, b.m);
for (int i = 1; i <= a.n; i++) for (int j = 1; j <= b.m; j++)
for (int k = 1; k <= a.m; k++)
if (a.a[i][k] != -1 && b.a[k][j] != -1)
res.a[i][j] = Max(res.a[i][j], a.a[i][k] + b.a[k][j]);
return res;
}
} F, A[32];
struct orz
{
int t, x, y;
} a[E];
inline bool comp(orz a, orz b)
{
return a.t < b.t;
}
int o(int u, int id) {return (u - 1) * 5 + id;}
int main()
{
#ifdef ONLINE_JUDGE
freopen("delicacy.in", "r", stdin);
freopen("delicacy.out", "w", stdout);
#endif
int x, y, z;
read(n); read(m); read(T); read(k);
for (int i = 1; i <= n; i++) read(c[i]);
A[0] = matrix(n * 5, n * 5); F = matrix(1, n * 5);
while (m--) read(x), read(y), read(z),
A[0].a[o(x, z)][o(y, 1)] = Max(A[0].a[o(x, z)][o(y, 1)], 1ll * c[y]);
for (int u = 1; u <= n; u++) for (int id = 1; id <= 4; id++)
A[0].a[o(u, id)][o(u, id + 1)] = 0;
F.a[1][o(1, 1)] = c[1];
for (int i = 1; i <= k; i++) read(a[i].t), read(a[i].x), read(a[i].y);
std::sort(a + 1, a + k + 1, comp);
a[0] = (orz) {0, 1, 0}; a[++k] = (orz) {T, 1, 0};
for (int i = 1; i <= 29; i++) A[i] = A[i - 1] * A[i - 1];
for (int i = 1; i <= k; i++)
{
for (int j = 29; j >= 0; j--) if ((a[i].t - a[i - 1].t >> j) & 1)
F = F * A[j];
if (F.a[1][o(a[i].x, 1)] > 0) F.a[1][o(a[i].x, 1)] += a[i].y;
}
return std::cout << F.a[1][o(1, 1)] << std::endl, 0;
}
Destiny
Solution
为了方便，选边改成选点（根不能选），即 (u_i) 到 (v_i) 的路径上（含 (v_i)，不含 (u_i)）至少要选一个点。
考虑一个 DP：(f_{u,i}) 表示 (u) 的祖先中选出的最深的点深度为 (i)，覆盖终点在 (u) 子树内的所有路径的方案数，需要满足 (1le ilemax(1,dep_u-1))。
转移一：不选 (u) 点。（(md_u) 表示满足 (v_i=u) 的最大 (dep_{u_i})）
[f_{u,i}=prod_{vin son(u)}f_{v,i}>>>(md_u<ile dep_u)
]
转移二：选上 (u) 点。
[f_{u,i}+=f_{u,dep_u}>>>(i<dep_u)
]
之后如果 (u e 1) 就 (f_{u,dep_u}leftarrow0)，就能得到 (f_u)。
这样做完答案就是 (f_{1,1})，复杂度 (O(n^2))。
注意到第一种转移式左右的下标不变，第二种转移是区间加，故可以使用线段树合并，维护加和乘标记，区间清 (0) 时只需删掉对应节点即可，(O(nlog n))。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}
const int N = 5e5 + 5, M = N << 1, L = 6e7 + 5, EI = 998244353;
int n, m, ecnt, nxt[M], adj[N], go[M], dep[N], md[N], ToT;
struct node
{
int lc, rc, add, prod;
} T[L];
void add_edge(int u, int v)
{
nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
void dfs(int u, int fu)
{
dep[u] = dep[fu] + 1;
for (int e = adj[u], v; e; e = nxt[e])
if ((v = go[e]) != fu) dfs(v, u);
}
void down(int p)
{
if (!T[p].lc) T[T[p].lc = ++ToT].prod = 1;
if (!T[p].rc) T[T[p].rc = ++ToT].prod = 1;
T[T[p].lc].prod = 1ll * T[T[p].lc].prod * T[p].prod % EI;
T[T[p].rc].prod = 1ll * T[T[p].rc].prod * T[p].prod % EI;
T[T[p].lc].add = (1ll * T[T[p].lc].add * T[p].prod + T[p].add) % EI;
T[T[p].rc].add = (1ll * T[T[p].rc].add * T[p].prod + T[p].add) % EI;
T[p].add = 0; T[p].prod = 1;
}
int query(int l, int r, int pos, int p)
{
if (!p) return 0;
if (l == r) return T[p].add;
int mid = l + r >> 1, res = pos <= mid ? query(l, mid, pos, T[p].lc)
: query(mid + 1, r, pos, T[p].rc);
res = (1ll * res * T[p].prod + T[p].add) % EI;
return res;
}
void del(int l, int r, int s, int e, int &p)
{
if (e < l || s > r) return;
if (s <= l && r <= e) return (void) (p = 0);
int mid = l + r >> 1; down(p);
del(l, mid, s, e, T[p].lc); del(mid + 1, r, s, e, T[p].rc);
}
int merge(int x, int y)
{
if (!x || !y) return 0;
if (!T[x].lc && !T[x].rc)
return T[y].prod = 1ll * T[y].prod * T[x].add % EI,
T[y].add = 1ll * T[y].add * T[x].add % EI, y;
if (!T[y].lc && !T[y].rc)
return T[x].prod = 1ll * T[x].prod * T[y].add % EI,
T[x].add = 1ll * T[x].add * T[y].add % EI, x;
down(x); down(y);
T[x].lc = merge(T[x].lc, T[y].lc);
T[x].rc = merge(T[x].rc, T[y].rc);
return x;
}
void change(int l, int r, int s, int e, int v, int &p)
{
if (e < l || s > r) return;
if (!p) T[p = ++ToT].prod = 1;
if (s <= l && r <= e) return (void) (T[p].add = (T[p].add + v) % EI);
int mid = l + r >> 1; down(p);
change(l, mid, s, e, v, T[p].lc);
change(mid + 1, r, s, e, v, T[p].rc);
}
int dp(int u, int fu)
{
int rt = 0; change(1, n, 1, n, 1, rt);
for (int e = adj[u], v; e; e = nxt[e], v = go[e])
if ((v = go[e]) != fu) rt = merge(rt, dp(v, u));
if (md[u]) del(1, n, 1, md[u], rt);
if (u > 1) change(1, n, 1, dep[u] - 1, query(1, n, dep[u], rt), rt),
del(1, n, dep[u], dep[u], rt);
return rt;
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("destiny.in", "r", stdin);
freopen("destiny.out", "w", stdout);
#endif
int x, y;
read(n);
for (int i = 1; i < n; i++) read(x), read(y), add_edge(x, y);
dfs(1, 1); read(m);
while (m--) read(x), read(y), md[y] = Max(md[y], dep[x]);
return std::cout << query(1, n, 1, dp(1, 0)) << std::endl, 0;
}
Tears
Solution
这里提供一个分块的做法。
为了方便，下面 (r_{i,1},r_{i,2},c_{i,1},c_{i,2}) 分别用 (lx,rx,ly,ry) 代替。
考虑把二维矩形拆成 (4) 个前缀容斥的形式，设 (f(x,y)) 表示矩形 ((1,1)-(x,y)) 内满足关系的点对数，(g(lx_1,rx_1,ly_1,ry_1,lx_2,rx_2,ly_2,ry_2)) 表示第一个点在矩形 ((lx_1,ly_1)-(rx_1,ry_1)) 内，第二个点在矩形 ((lx_2,ly_2)-(rx_2,ry_2)) 内，合法的点对数。
则大力容斥可以得到答案可以表示成：
[f(rx,ry)-f(lx-1,ry)-f(rx,ly-1)+f(lx-1,ly-1)
]
[-g(1,lx-1,1,ry,lx,rx,1,ry)+g(1,lx-1,1,ly-1,lx,rx,1,ly-1)
]
[-g(1,rx,1,ly-1,1,rx,ly,ry)+g(1,lx-1,1,ly-1,1,lx-1,ly,ry)
]
[+g(1,lx-1,1,ly-1,lx,rx,ly,ry)
]
(f) 可以直接二维数点，(g(1,lx-1,1,ly-1,lx,rx,ly,ry)) 的第一个矩形严格在第二个矩形左下方，可以直接用两个矩形内的点数乘起来。
于是问题转化成给定 (y,l,r)，求纵坐标 (le y) 的区域内，第一个点的横坐标在 ([1,l-1])，第二个点的横坐标在 ([l,r]) 的点对数。
考虑按 (y) 分块。设 (y) 在第 (b) 块内，分几类：、
（1）两个点来自不同的块，且都不在第 (b) 块：枚举第二个点所在的块，容易发现这种情况对答案的贡献可以描述成两个矩形内点数的乘积，直接计算即可。
（2）第二个点在第 (b) 块，第一个点不在第 (b) 块：与（1）类似，只不过第二个点的纵坐标有了个 (y) 的限制，这里可以暴力枚举第 (b) 块内的所有点进行统计。
（3）两个点都在第 (i e b) 块：由于一个块内的点数为 (O(sqrt n))，故对于一个特定的 (i)，本质不同的询问只有 (O(n)) 种，可以事先预处理。
（4）两个点都在第 (b) 块：暴力枚举第 (b) 块内的点即可。为了避免算顺序对的复杂度多 (log)，需要把块内的点提前按 (y) 排序，每次询问时用双指针扫。
具体实现时可以离线后从小到大枚举 (b)，每到一个 (b) 就对所有相关询问都处理一遍，这样可以使得空间为 (O(n+m))，具体细节见代码 jiejuediao 函数。
时间复杂度 (O((n+m)sqrt n))。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
typedef long long ll;
const int N = 1e5 + 5, M = N << 1, L = M << 1, E = 350;
int n, m, S, p[N], q[N], c1[M], c2[M], B[N], tot, bl[E], br[E], in[N], cur[N],
lx[M], rx[M], ly[M], ry[M], sum[N], cnt, a[E], b[E][E], lt[N];
ll ans[M], A[N], f[N];
void changeA(int x, ll v)
{
for (; x <= n; x += x & -x)
A[x] += v;
}
ll askA(int x)
{
ll res = 0;
for (; x; x -= x & -x) res += A[x];
return res;
}
void changeB(int x, int v)
{
for (; x <= n; x += x & -x)
B[x] += v;
}
int askB(int x)
{
int res = 0;
for (; x; x -= x & -x) res += B[x];
return res;
}
struct query
{
int id, t, l, r;
} que1[L];
void jiejuediao()
{
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= tot; i++)
{
cnt = 0;
for (int j = 1; j <= n; j++)
{
cur[j] = cur[j - 1]; lt[j] = lt[j - 1];
if (in[p[j]] == i) cur[j]++, a[++cnt] = j, lt[j] = cnt;
}
for (int j = 1; j <= cnt; j++)
for (int k = 1; k <= cnt; k++)
b[j][k] = b[j - 1][k] + b[j][k - 1] - b[j - 1][k - 1]
+ (p[a[j]] < p[a[k]]);
std::sort(a + 1, a + cnt + 1, [&](int x, int y) {return p[x] < p[y];});
for (int j = 1; j <= m; j++)
{
int l = lx[j] - 1, r = rx[j];
if (in[ry[j]] > i) ans[j] -= 1ll * (cur[r] - cur[l])
* sum[l] + b[lt[l]][lt[r]] - b[lt[l]][lt[l]];
if (in[ly[j] - 1] > i) ans[j] += 1ll * (cur[r] - cur[l])
* sum[l] + b[lt[l]][lt[r]] - b[lt[l]][lt[l]];
if (in[ry[j]] == i)
{
int s = 0;
for (int k = 1, h = 1, c = 0; k <= cnt && p[a[k]] <= ry[j]; k++)
if (l < a[k] && a[k] <= r)
{
s++;
while (h <= cnt && p[a[h]] < p[a[k]])
{
if (a[h] <= l) c++;
h++;
}
ans[j] -= c;
}
ans[j] -= 1ll * s * sum[l];
}
if (in[ly[j] - 1] == i)
{
int s = 0;
for (int k = 1, h = 1, c = 0; k <= cnt && p[a[k]] < ly[j]; k++)
if (l < a[k] && a[k] <= r)
{
s++;
while (h <= cnt && p[a[h]] < p[a[k]])
{
if (a[h] <= l) c++;
h++;
}
ans[j] += c;
}
ans[j] += 1ll * s * sum[l];
}
}
for (int j = 1; j <= n; j++) sum[j] += cur[j];
}
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("tears.in", "r", stdin);
freopen("tears.out", "w", stdout);
#endif
int xl, xr, yl, yr;
read(n); read(m); S = sqrt(n);
for (int i = 1; i <= n; i += S) bl[++tot] = i,
br[tot] = i + S - 1 < n ? i + S - 1 : n;
for (int i = 1; i <= n; i++) read(p[i]), q[p[i]] = i,
in[i] = (i - 1) / S + 1;
for (int i = 1; i <= n; i++) f[i] = askB(p[i]), changeB(p[i], 1);
for (int i = 1; i <= m; i++)
{
read(xl); read(xr); read(yl); read(yr);
lx[i] = xl; rx[i] = xr; ly[i] = yl; ry[i] = yr;
que1[i] = (query) {-i, xl - 1, yl, yr};
que1[i + m] = (query) {i, xr, yl, yr};
}
std::sort(que1 + 1, que1 + (m << 1) + 1, [&](query a, query b)
{return a.t < b.t;});
memset(B, 0, sizeof(B));
for (int i = 1, j = 1; i <= (m << 1); i++)
{
while (j <= que1[i].t) changeA(p[j], f[j]), changeB(p[j], 1), j++;
ll delta = askA(que1[i].r) - askA(que1[i].l - 1);
int d1 = askB(que1[i].r), d2 = askB(que1[i].l - 1);
if (que1[i].id < 0) ans[-que1[i].id] -= delta, c1[-que1[i].id] = d2,
c2[-que1[i].id] -= d1 - d2;
else ans[que1[i].id] += delta, c2[que1[i].id] += d1 - d2;
}
jiejuediao();
for (int i = 1; i <= n; i++) p[i] = q[i];
for (int i = 1; i <= m; i++) std::swap(lx[i], ly[i]),
std::swap(rx[i], ry[i]);
jiejuediao();
for (int i = 1; i <= m; i++)
printf("%lld
", ans[i] + 1ll * c1[i] * c2[i]);
return 0;
}
Meal
Solution
结论 (1)：若 (m=n-1) 则合法方案一定存在。
证明：容易发现最小的数不超过 (k)，最小数和最大数之和不少于 (k)（(nge 2)），当 (n>2) 时取走最小数加上最大数的一部分凑成 (k)，就能得到 (n) 和 (m) 都减少 (1) 的情况，然后继续这样的操作直到 (m) 变成 (0)。
于是 (mge n-1) 时可以加入 (m-n-1) 个 (0)，用 std::set 维护当前的数，就能做到 (O(mlog m))。
结论 (2)：若 (m=n-2) 则可以把这 (n) 个数拆成两个满足 (m=n-1) 的集合。
证明：考虑在每次操作的两个数之间连边构成一个图，显然 (n) 点 (n-2) 边的图不连通，且存在一个连通块是树，让这棵树成为其中一个集合，就能达到目的。
一个子集 (S) 合法的条件为 (sum_{iin S}d_i=(|S|-1)k)，移一下项得 (sum_{iin S}(k-d_i)=k)。
可以通过 bitset 优化背包 DP 来得到是否存在这样的子集，把 DP 倒着推回去可以得到一个合法子集，这里的复杂度为 (O(frac{n^3}{omega}))。
然后对两个子集分别跑一遍 (m=n-1) 即可。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
const int N = 505, M = 5e6 + 5;
int n, m, k, d[N];
std::bitset<M> f[N];
struct orz
{
int i, x, j, y;
friend inline bool operator < (orz a, orz b)
{
return a.x < b.x;
}
};
std::vector<orz> ans;
void nealchen(std::vector<orz> d, int m)
{
while (d.size() <= m) d.push_back((orz) {0, 0, 0, 0});
std::multiset<orz> pq;
for (int i = 0; i < d.size(); i++) pq.insert(d[i]);
while (m--)
{
std::multiset<orz>::iterator fi = pq.begin(), ls = pq.end(); ls--;
int t1 = ls->i, t2 = ls->x - (k - fi->x);
ans.push_back((orz) {fi->i, fi->x, ls->i, k - fi->x});
pq.erase(fi); pq.erase(ls); pq.insert((orz) {t1, t2, 0, 0});
}
}
void output()
{
for (int i = 0; i < ans.size(); i++)
{
if (ans[i].x) printf("%d %d ", ans[i].i, ans[i].x);
if (ans[i].y) printf("%d %d ", ans[i].j, ans[i].y);
puts("");
}
}
void work()
{
read(n); read(m); read(k); ans.clear();
for (int i = 1; i <= n; i++) read(d[i]);
if (m >= n - 1)
{
std::vector<orz> a;
for (int i = 1; i <= n; i++) a.push_back((orz) {i, d[i], 0, 0});
nealchen(a, m); return output();
}
std::vector<orz> ia, ib; f[0].reset(); f[0][n * k] = 1;
for (int i = 1; i <= n; i++)
{
f[i] = f[i - 1];
if (k - d[i] >= 0) f[i] |= f[i - 1] << k - d[i];
else f[i] |= f[i - 1] >> d[i] - k;
}
if (!f[n][(n + 1) * k]) return (void) puts("-1");
for (int i = n, cur = (n + 1) * k; i >= 1; i--)
if (f[i - 1][cur]) ia.push_back((orz) {i, d[i], 0, 0});
else ib.push_back((orz) {i, d[i], 0, 0}), cur -= k - d[i];
if (ia.size() > 1) nealchen(ia, ia.size() - 1);
if (ib.size() > 1) nealchen(ib, ib.size() - 1);
output();
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("dish.in", "r", stdin);
freopen("dish.out", "w", stdout);
#endif
int T; read(T);
while (T--) work();
return 0;
}
Surreal
Solution
出题人：可能有的选手第一遍会看错成叶子能随便加。对于叶子能随便加的版本，大概会稍微好做一点点。
题目要求的就是是否对于所有的深度 (h) 都存在一棵树不能被所有模板树生长得到。
结论：深度为 (h) 的不能被生长得到的树若存在，则存在一棵树，满足这棵树能够在一条深度为 (h) 的链上的部分位置各插入一个叶子得到。
证明略。
显然地，有了这个结论之后，我们就只要保留具有这种结构的模板树。
一棵具有这种结构的树可以用一个数字串表示：从上到下，(0) 表示没有右子树，(1) 表示右子树为叶子，(2) 表示没有左子树，(3) 表示左子树为叶子，(4) 表示左右子树都为叶子。
这样每棵模板树都可以被表示成一个 (0sim3) 的数字串（最后一个数可以为 (4)）。
这个 (4) 很讨厌，但不难发现在这种情况下模板树如果要生长，则这个 (4) 必然要变成 (1) 或 (3)，所以形如 (s4) 的模板树可以拆成两棵，即 (s1) 和 (s3)。
这样问题就转化成对于一个足够大的 (l)，是否满足所有串长为 (l) 的 (0sim3) 数字串都包含模板串之一为前缀。
Trie 上 DFS 即可，复杂度是线性的。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
const int N = 2e6 + 5, M = 1e7 + 5;
int n, cnt, lc[N], rc[N], sze[N], ToT;
bool is, f[M];
std::vector<int> seq[N];
struct trie
{
int son[4]; bool mark;
void init() {son[0] = son[1] = son[2] = son[3] = 0; mark = 0;}
} T[M];
void dfs(int u)
{
sze[u] = 1;
if (lc[u]) dfs(lc[u]), sze[u] += sze[lc[u]];
if (rc[u]) dfs(rc[u]), sze[u] += sze[rc[u]];
if (sze[lc[u]] > 1 && sze[rc[u]] > 1) is = 0;
}
void sfd(int u, int th)
{
if (lc[u] && !rc[u]) seq[th].push_back(0), sfd(lc[u], th);
if (sze[lc[u]] > 1 && sze[rc[u]] == 1) seq[th].push_back(1), sfd(lc[u], th);
if (rc[u] && !lc[u]) seq[th].push_back(2), sfd(rc[u], th);
if (sze[rc[u]] > 1 && sze[lc[u]] == 1) seq[th].push_back(3), sfd(rc[u], th);
if (sze[lc[u]] == 1 && sze[rc[u]] == 1)
seq[th].push_back(5);
}
void ins(std::vector<int> s)
{
int u = 1;
for (int i = 0; i < s.size(); i++)
{
if (!T[u].son[s[i]]) T[T[u].son[s[i]] = ++ToT].init();
u = T[u].son[s[i]];
}
T[u].mark = 1;
}
void solve(int u)
{
f[u] = T[u].mark; bool o = 1;
for (int c = 0; c < 4; c++)
{
if (T[u].son[c]) solve(T[u].son[c]);
o &= f[T[u].son[c]];
}
f[u] |= o;
}
void work()
{
int m; read(m); cnt = 0;
while (m--)
{
read(n);
for (int i = 1; i <= n; i++) read(lc[i]), read(rc[i]);
is = 1; dfs(1);
if (is) seq[++cnt].clear(), sfd(1, cnt);
}
T[ToT = 1].init();
for (int i = 1; i <= cnt; i++)
if (!seq[i].empty() && seq[i][seq[i].size() - 1] == 5)
{
seq[i][seq[i].size() - 1] = 1; ins(seq[i]);
seq[i][seq[i].size() - 1] = 3; ins(seq[i]);
}
else ins(seq[i]);
puts((solve(1), f[1]) ? "Almost Complete" : "No");
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("surreal.in", "r", stdin);
freopen("surreal.out", "w", stdout);
#endif
int T; read(T);
while (T--) work();
return 0;
}
Road
不会，咕了。