题意精简

• 给一棵树，每条边可以定向为 u→v（用 0 表示）或 v→u（用 1 表示）
• 有 m 个限制 (a_i, b_i)，要求 a_i 不能到达 b_i
• 求字典序最小的 01 串表示边的方向

核心思路

关键转化：
对于限制 (a, b)，a 到 b 的唯一路径上至少有一条边是反向的（不能全部顺着 a→b 方向）。

贪心策略：
按输入顺序处理每条边，尽量设为 0，除非会违反限制才设为 1。

算法步骤

1. 预处理

   • 建树，DFS 求深度、父节点、DFS 序
   • 预处理 LCA（倍增法）

2. 限制处理
   对每个限制 (a, b)，标记整条路径：如果某条边方向与 a→b 一致，就会违反限制。

3. 贪心定向
   对于边 (u, v)：

   • 尝试设为 u→v（0）
   • 检查是否会使某个限制 (a, b) 的路径全部同向
   • 如果会，则必须设为 v→u（1）
   • 确定方向后，更新相关限制的状态

4. 输出
   按顺序输出每条边的 0/1

复杂度

• 时间：O((n+m) log n)
• 空间：O(n log n)

示例代码框架

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+5, LOG = 20;

int n, m;
vector<pair<int,int>> g[N];
int eu[N], ev[N], ans[N];
int dep[N], par[N][LOG], in[N], out[N], timer;

void dfs(int u, int p) {
    in[u] = ++timer;
    par[u][0] = p;
    for (int i = 1; i < LOG; i++) 
        par[u][i] = par[par[u][i-1]][i-1];
    for (auto [v, id] : g[u]) {
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
    out[u] = timer;
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int d = dep[a] - dep[b];
    for (int i = 0; i < LOG; i++)
        if (d >> i & 1) a = par[a][i];
    if (a == b) return a;
    for (int i = LOG-1; i >= 0; i--)
        if (par[a][i] != par[b][i])
            a = par[a][i], b = par[b][i];
    return par[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int c;
    cin >> c >> n >> m;
    for (int i = 1; i < n; i++) {
        cin >> eu[i] >> ev[i];
        g[eu[i]].push_back({ev[i], i});
        g[ev[i]].push_back({eu[i], i});
    }
    
    dfs(1, 1);
    
    // 这里需要实现限制的存储和检查逻辑
    // 实际实现会用树上差分 + 树状数组来高效判断冲突
    
    for (int i = 1; i < n; i++) {
        // 贪心：先尝试 0，冲突则选 1
        ans[i] = 0; // 实际需要检查冲突
    }
    
    for (int i = 1; i < n; i++) cout << ans[i];
    cout << "\n";
    
    return 0;
}

核心难点

• 高效判断某条边方向是否违反限制
• 使用树上差分快速标记和查询限制的影响范围
• 保证贪心的正确性

这样就能在 O(n log n) 级别解决该问题。