2019 树上的数 · 方案二贪心定序加时刻链

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 4985 字
逐位贪心定 P，给每条边分配合法的删除时刻
2019
树
正文

// CSP-S 2019 复赛 T3 · 树上的数（方案二：贪心定序 + 时刻链检查）
// 原题：https://oj.yecheng.tv/p/CSPS2019C
// 题意：同方案一（n ≤ 2000，T ≤ 10）。删除边 e 时仅交换 e 两端的数字。
// 思路（逐位贪心确定 P + 删除时刻分配）：
//   数字 d 从起点 s 移到目标 q，必须沿一条路径 s→q，且路径边 e1..ek
//   的删除时刻 t1 < t2 < ... < tk（每删一条边数字沿边移动一格）。
//   "停靠点不被打扰"约束：
//   - 中间点 x_j 在时刻 t_j 与 t_{j+1} 之间停着数字 d，故 x_j 上其它
//     已定时刻的边不能落在 (t_j, t_{j+1}) 内；
//   - 起点 s：其它已定边必须 > t1（否则 d 停在 s 期间被换走）；
//   - 终点 q：其它已定边必须 < tk（到达后不许再被换走）。
//   关键简化：若 t_{j+1} 取"大于 t_j 的最小空闲时刻"，则开区间
//   (t_j, t_{j+1}) 内天然没有任何已用时刻 → 中间点约束自动满足。
//   于是只需枚举 t1（必须空闲且小于 s 上所有已定时刻），随后链式
//   取最小空闲；最后校验 tk > q 上所有已定时刻。
//   贪心流程：按 d = 1..n 逐位，q 从小到大试，第一个可行的 q 即答案。
// 复杂度：O(T · n^2 · k)（k 为路径长），n ≤ 160 的测试点可过；
//   满分还需把"链式取时刻"换成 O(1) 的数据结构（注释口径）。
// 易错点：
//   1. t1 的候选从小到大试，一旦违反 s 约束只能换更大的 t1；
//   2. tk 约束失败时要回溯换 t1 重试，全部失败则 q 不可行；
//   3. 提交成功的时刻分配要写入 usedT 与两端点的时刻表；
//   4. q == s 时数字不动，直接锁定。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int T, n;
int eu[2005], ev[2005];
int numAt[2005], where[2005];
vector<int> g[2005];
bool usedT[2005];
vector<int> pt[2005];                  // 每个点关联边的已定时刻
int ansP[2005];

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            g[i].clear();
            pt[i].clear();
        }
        for (int i = 1; i < n; i++) scanf("%d%d", &eu[i], &ev[i]);
        for (int d = 1; d <= n; d++) {
            scanf("%d", &numAt[d]);
            where[numAt[d]] = d;
        }
        memset(usedT, 0, sizeof(usedT));
        memset(ansP, 0, sizeof(ansP));
        // 按数字 1..n 逐位贪心
        for (int d = 1; d <= n; d++) {
            int s = where[d];
            bool fixed = false;
            for (int q = 1; q <= n && !fixed; q++) {
                if (q == s) { ansP[d] = q; fixed = true; break; }
                // BFS 找 s->q 路径
                static int fa[2005], que[2005];
                static bool vis[2005];
                for (int i = 1; i <= n; i++) vis[i] = false;
                int head = 0, tail = 0;
                que[tail++] = s;
                vis[s] = true;
                fa[s] = 0;
                while (head < tail) {
                    int u = que[head++];
                    if (u == q) break;
                    for (int e : g[u]) {
                        int v = eu[e] ^ ev[e] ^ u;
                        if (!vis[v]) { vis[v] = true; fa[v] = u; que[tail++] = v; }
                    }
                }
                if (!vis[q]) continue;
                // 收集路径边（q 回溯到 s，再反转）
                vector<int> seq;
                for (int u = q; u != s; u = fa[u])
                    for (int e : g[u])
                        if ((eu[e] ^ ev[e] ^ u) == fa[u]) { seq.push_back(e); break; }
                reverse(seq.begin(), seq.end());
                int k = (int)seq.size();
                // s 上非路径已定边的最大时刻：t1 必须比它小
                int sLimit = n;
                {
                    static bool onPath[2005];
                    memset(onPath, 0, sizeof(onPath));
                    for (int e : seq) onPath[e] = true;
                    for (int e : g[s])
                        if (!onPath[e])
                            for (int t : pt[s]) { sLimit = t; break; }
                }
                // q 上非路径已定边的最大时刻：tk 必须比它大
                int qLimit = 0;
                {
                    static bool onPath[2005];
                    memset(onPath, 0, sizeof(onPath));
                    for (int e : seq) onPath[e] = true;
                    for (int e : g[q])
                        if (!onPath[e])
                            for (int t : pt[q]) qLimit = max(qLimit, t);
                }
                // 枚举 t1（从小到大），链式取最小空闲
                static int assign[2005];
                bool done = false;
                for (int t1 = 1; t1 < n && !done; t1++) {
                    if (usedT[t1] || t1 >= sLimit) break;
                    assign[1] = t1;
                    bool okchain = true;
                    for (int j = 2; j <= k; j++) {
                        int t = assign[j - 1] + 1;
                        while (t < n && usedT[t]) t++;
                        if (t >= n) { okchain = false; break; }
                        assign[j] = t;
                    }
                    if (!okchain || assign[k] <= qLimit) continue;
                    // 提交分配
                    for (int j = 1; j <= k; j++) {
                        int e = seq[j - 1];
                        usedT[assign[j]] = true;
                        pt[eu[e]].push_back(assign[j]);
                        pt[ev[e]].push_back(assign[j]);
                    }
                    ansP[d] = q;
                    fixed = true;
                    done = true;
                }
            }
        }
        for (int d = 1; d <= n; d++) printf("%d%c", ansP[d], d == n ? '\n' : ' ');
    }
    return 0;
}
2019 树上的数 · 方案二 贪心定序加时刻链

正文

CSP-S 标程 · 复赛真题的其它内容

2019 树上的数 · 方案二贪心定序加时刻链
