问题分析

我们有一棵树，初始所有边都是土路。有两种操作：

• A a b：将边 (a,b) 改为公路
• W a：查询从根节点 1 到节点 a 的路径上剩余的土路数量

关键思路

1. 问题转化

从根节点到任意节点的路径上的土路数量，等于路径长度减去路径上已改为公路的边数。

由于树有 $n$ 个节点，从根到任意节点的路径长度是固定的（深度），所以问题转化为：

• 初始时所有边都是土路
• 每次将一条边改为公路
• 查询路径上还有多少土路

2. 利用DFS序

通过DFS遍历给每个节点分配时间戳：

• s[x]：节点 x 的DFS进入时间
• t[x]：节点 x 的DFS离开时间

对于树边 (u, v)（假设 u 是 v 的父节点），可以用节点 v 来代表这条边。

算法设计

核心思想：差分数组 + 树状数组

1. 初始化：所有边都是土路，在树状数组中对每个边对应的区间 [s[v], t[v]] 加1
2. 查询操作：查询节点 x 的值，就是根到 x 路径上的土路数量
3. 更新操作：将边改为公路时，在对应区间减1

为什么这样正确？

考虑边 (u, v)，其中 u 是 v 的父节点：

• 这条边影响所有以 v 为根的子树中的节点
• 当从根到某个节点的路径经过这条边时，该节点在 v 的子树中
• 因此在 [s[v], t[v]] 区间加1，表示这些节点到根的路径包含这条土路

代码详细解析

1. DFS预处理

void S(int x, int p) {
    s[x] = ++top;  // DFS进入时间
    for (int i : e[x]) {
        if (i != p)
            S(i, x);
    }
    t[x] = top;    // DFS离开时间
}

2. 初始化树状数组

for (int i = 2; i <= n; i++)
    Tr.A(s[i], 1), Tr.A(t[i] + 1, -1);

这里对每个节点 i（除了根节点）代表的边，在区间 [s[i], t[i]] 上加1。

3. 查询操作

if (ty == 'W') {
    cout << Tr.Q(s[x]) << '\n';
}

查询节点 x 在树状数组中的值，即根到 x 路径上的土路数量。

4. 更新操作

if (ty == 'A') {
    cin >> y;
    Tr.A(s[max(x, y)], -1), Tr.A(t[max(x, y)] + 1, 1);
}

将边 (x,y) 改为公路时，找到子节点（max(x,y) 在DFS序中较大），在对应区间减1。

正确性证明

查询操作

对于节点 x，树状数组在位置 s[x] 的值等于所有包含 x 的区间之和。由于DFS序的性质，包含 s[x] 的区间恰好对应根到 x 路径上的所有边。

更新操作

当边 (u,v) 改为公路时（v 是子节点），我们取消这条边对所有 v 的子树中节点的贡献。

复杂度分析

• DFS预处理：$O(n)$
• 每次查询/更新：$O(\log n)$
• 总复杂度：$O((n+m)\log n)$

样例验证

输入树结构：

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

DFS序：

节点: 1  2  3  4  5
s[]: 1  2  4  5  6
t[]: 7  2  4  7  6

执行过程：

1. W 5：查询根到5的路径，输出2（初始土路数）
2. A 1 4：将边(1,4)改为公路
3. W 5：输出1（少了一条土路）
4. A 4 5：将边(4,5)改为公路
5. W 5：输出0（所有边都是公路了）
6. W 2：输出1（根到2的路径还有土路）

总结

本题通过DFS序将树结构转化为线性序列，利用树状数组维护差分数组，高效支持路径查询和边更新操作。这种"DFS序 + 树状数组"的组合是处理树上路径问题的经典技巧。