BalticOI 2019 Alpine Valley 题解

题目分析

这道题要求处理树上的动态查询：当某条边被封锁时，判断从某村庄能否到达出口，否则求到最近商店的距离。

关键点：

• 树结构，边有权重
• 有指定出口节点 $E$
• 部分节点有商店
• 查询：封锁某边后从某节点出发的情况

解题思路

核心观察

1. 树的性质：封锁一条边会将树分成两个连通分量
2. 问题转化：如果查询节点和出口 $E$ 在封锁边的同一侧，则可以逃脱；否则需要找最近商店
3. 重标号技巧：使用DFS序将树转化为序列问题

算法设计

代码采用了DFS序 + 线段树 + 树形遍历的方法：

主要步骤：

1. DFS预处理：计算每个节点的DFS序、子树范围、深度
2. 线段树构建：维护每个节点到最近商店的距离
3. 树形DP：通过遍历更新线段树，处理边封锁的影响

代码详解

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

int n, s, q, root;
typedef pair<int, ll> edge;
vector<edge> v[100005];
bool sho[100005];  // 标记是否有商店
int e[100005][2], dfn[100005], dc = 0, od[100005], re[100005];
ll dep[100005];    // 节点深度（到根的距离）
const ll inf = 1e18;
ll ans[100005];

struct node {
    int pth, id;
};
vector<node> qu[100005];  // 存储查询

// DFS预处理：计算DFS序和子树范围
void getdfn(int pos, int fa) {
    dfn[pos] = ++dc;
    re[dc] = pos;

    for (auto u : v[pos]) {
        if (u.first == fa) continue;
        dep[u.first] = dep[pos] + u.second;
        getdfn(u.first, pos);
    }
    od[pos] = dc;  // 子树结束时间戳
}

// 线段树部分
ll tr[400005], tag[400005];
#define ls (d<<1)
#define rs (d<<1)|1

void build(int l, int r, int d) {
    if (l == r) {
        // 有商店的节点值为深度，否则为无穷大
        tr[d] = (sho[re[l]] ? dep[re[l]] : inf + inf);
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    tr[d] = min(tr[ls], tr[rs]);
}

void pushdown(int d) {
    tr[ls] += tag[d];
    tr[rs] += tag[d];
    tag[ls] += tag[d];
    tag[rs] += tag[d];
    tag[d] = 0;
}

// 区间更新
void update(int l, int r, int nl, int nr, ll val, int d) {
    if (l > r) return;
    if (l <= nl && nr <= r) {
        tr[d] += val;
        tag[d] += val;
        return;
    }
    int mid = (nl + nr) >> 1;
    pushdown(d);
    if (l <= mid) update(l, r, nl, mid, val, ls);
    if (mid + 1 <= r) update(l, r, mid + 1, nr, val, rs);
    tr[d] = min(tr[ls], tr[rs]);
}

// 区间查询
ll query(int l, int r, int nl, int nr, int d) {
    if (l <= nl && nr <= r) return tr[d];
    int mid = (nl + nr) >> 1;
    ll res = inf + inf;
    pushdown(d);
    if (l <= mid) res = query(l, r, nl, mid, ls);
    if (mid + 1 <= r) res = min(res, query(l, r, mid + 1, nr, rs));
    return res;
}

// 判断wp是否是pos的子孙
bool isson(int pos, int wp) {
    return dfn[pos] <= dfn[wp] && dfn[wp] <= od[pos];
}

// 树形遍历处理查询
void solve(int pos, int fa) {
    // 处理当前节点的所有查询
    for (auto u : qu[pos]) {
        if (!isson(e[u.pth][1], pos)) 
            // 查询节点和出口在同一连通分量
            ans[u.id] = -1;
        else 
            // 查询封锁边子树内的最小商店距离
            ans[u.id] = query(dfn[e[u.pth][1]], od[e[u.pth][1]], 1, n, 1);
    }

    // 遍历子节点
    for (auto u : v[pos]) {
        if (u.first == fa) continue;
        
        // 更新线段树：整体增加边权，子树减少2倍边权
        update(1, n, 1, n, u.second, 1);
        update(dfn[u.first], od[u.first], 1, n, -2 * u.second, 1);
        
        solve(u.first, pos);
        
        // 恢复
        update(1, n, 1, n, -u.second, 1);
        update(dfn[u.first], od[u.first], 1, n, 2 * u.second, 1);
    }
}

void wk() {
    cin >> n >> s >> q >> root;
    
    // 读入边
    for (int i = 1, x, y, z; i <= n - 1; ++i) {
        cin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
        e[i][0] = x, e[i][1] = y;
    }
    
    // 读入商店位置
    for (int i = 1, x; i <= s; ++i) {
        cin >> x;
        sho[x] = true;
    }
    
    // DFS预处理
    getdfn(root, -1);
    
    // 调整边方向：使e[i][1]为子节点
    for (int i = 1; i <= n - 1; ++i)
        if (dep[e[i][0]] > dep[e[i][1]])
            swap(e[i][0], e[i][1]);
    
    // 构建线段树
    build(1, n, 1);
    
    // 读入查询
    for (int i = 1, x, y; i <= q; ++i) {
        cin >> x >> y;
        qu[y].push_back({x, i});
    }
    
    // 处理查询
    solve(root, -1);
    
    // 输出结果
    for (int i = 1; i <= q; ++i) {
        if (ans[i] == -1)
            cout << "escaped\n";
        else if (ans[i] >= inf)
            cout << "oo\n";
        else
            cout << ans[i] << endl;
    }
}

算法原理详解

1. 问题分析

当边 $I$ 被封锁时：

• 如果 $R$ 和 $E$ 在边的同一侧：可以逃脱
• 否则：$R$ 被隔离，需要找最近商店

2. 线段树作用

线段树维护每个DFS位置对应的节点到根节点路径上最近商店的距离。

关键操作：

• update(1, n, 1, n, u.second, 1)：所有节点增加边权
• update(dfn[u.first], od[u.first], 1, n, -2 * u.second, 1)：子树减少2倍边权

这样操作后，子树外的节点距离增加 $w$，子树内的节点距离减少 $w$，相当于改变了根节点。

3. 查询处理

对于查询 $(I, R)$：

• 检查 $R$ 是否在边 $I$ 的子节点一侧
• 如果在：查询该子树内最小商店距离
• 如果不在：可以逃脱

复杂度分析

• 时间复杂度：$O((n+q)\log n)$
• 空间复杂度：$O(n)$

样例解析

样例1：

5 2 3 1
1 2 3
1 3 2  
3 4 1
3 5 2
2
4
2 2
2 5
4 5

• 查询1：边2封锁，从节点2出发 → 与出口1同侧 → escaped
• 查询2：边2封锁，从节点5出发 → 被隔离，最近商店距离3
• 查询3：边4封锁，从节点5出发 → 无法到达任何商店 → oo

关键技巧

1. DFS序应用：将树结构转化为序列问题
2. 根切换：通过线段树操作模拟根节点变化
3. 懒标记线段树：高效支持区间更新和查询
4. 离线处理：在树遍历过程中处理所有查询

总结

这道题的解题亮点：

1. 问题转化：将边封锁问题转化为连通性判断
2. 动态根节点：通过线段树操作支持根节点切换
3. 高效查询：利用树形结构特性优化查询处理
4. 统一处理：在线段树中同时维护距离和商店信息

算法通过巧妙的DFS序和线段树设计，在 $O(n\log n)$ 时间内解决了动态树查询问题，展示了处理树上路径问题的先进技术。