Following Directions (USACO Silver 2023 January)

Following Directions (USACO Silver 2023 January)

  1. 所有牛最终到达的每个饲料点都可以看作一棵树，因此所有饲料点构成一个森林。改变一个指示牌的方向，本质上就是把一个子树移动到另一棵树上。

  2. 对每个饲料点用 DFS 计算其子树的初始值（即子树大小），并计算整个森林的总代价。

  3. 当改变一个指示牌时，需要更新原树和新树上所有祖先节点的值，然后更新总代价。

不需要单独建树（邻接表），所有 DFS、数值维护和更新都可以原地完成。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, q;
char a[1505][1505];   // 0-based
int v[1505][1505];
int c[2][1505];       // c[0] is column N+1, c[1] is row N+1
int ans;
 
int dfs(int r, int c) {
    v[r][c] = r < n && c < n ? 1 : 0;
    if (r > 0 && a[r-1][c] == 'D') {
        v[r][c] += dfs(r-1, c);
    }
    if (c > 0 && a[r][c-1] == 'R') {
        v[r][c] += dfs(r, c-1);
    }
    return v[r][c];
}
 
void update(pi p, int val) {
    while (p.first < n && p.second < n) {
        v[p.first][p.second] += val;
        p = a[p.first][p.second] == 'R' ? pi(p.first, p.second+1) : pi(p.first+1, p.second);
    }
    if (p.second == n) {
        ans += val * c[0][p.first];
    } else {
        ans += val * c[1][p.second];
    }
}
 
int main() {
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%s", a[i]);
        scanf("%d", &c[0][i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[1][i]);
    }
    for (int i = 0; i < n; i++) {
        ans += dfs(i, n) * c[0][i];
        ans += dfs(n, i) * c[1][i];
    }
    printf("%d\n", ans);
 
    scanf("%d",&q);
    for (int i = 0; i < q; i++) {
        int r, c;
        scanf("%d %d", &r, &c);
        r--; c--;
        int val = v[r][c];
        update(a[r][c] == 'R' ? pi(r,c+1) : pi(r+1,c), -val);  // remove from old tree
        a[r][c] = a[r][c] == 'R' ? 'D' : 'R';              // change sign post
        update(a[r][c] == 'R' ? pi(r,c+1) : pi(r+1,c), val);   // add to new tree
 
        printf("%d\n", ans);
    }
    
    return 0;
}