问题分析

我们有一个 $N$ 个节点的有向图，每个节点：

• 有一个价值 $A_i$
• 有一条出边指向 $F_i$（可能指向自己）

从每个节点 $i$ 出发，沿着出边走，求访问到的不同节点的价值总和最大值。

关键点：访问多次的节点只计算一次价值。

算法思路

核心思想：Tarjan强连通分量 + 记忆化搜索

将问题分解为两个部分：

1. 环处理：强连通分量（环）内的节点答案相同，为环内所有节点价值之和
2. 链处理：环外节点（树节点）的答案为自身价值加上后续节点的答案

算法步骤

1. 环检测与处理（Tarjan算法）

使用Tarjan算法找出所有强连通分量（环）：

• 环内所有节点的答案 = 环内所有节点价值之和
• 因为一旦进入环，就会遍历环中所有节点

2. 链处理（记忆化搜索）

对于不在环中的节点：

• 自环节点：答案 = 自身价值
• 树节点：答案 = 自身价值 + 下一个节点的答案

代码详解

1. 数据结构和初始化

const int N = 200050;
int a[N];        // 节点价值
int to[N];       // 出边指向
int ans[N];      // 存储最终答案
int low[N], dfn[N], in[N], sta[N];  // Tarjan算法相关

2. Tarjan算法找强连通分量

void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;    // 初始化时间戳
    in[x] = 1;                  // 标记入栈
    sta[++top] = x;             // 节点入栈
    
    int y = to[x];              // 下一个节点
    
    if (!dfn[y]) {              // 未访问过，递归处理
        tarjan(y);
        low[x] = min(low[x], low[y]);
    } else if (in[y]) {         // 已在栈中，形成环
        low[x] = min(low[x], dfn[y]);
    }
    
    // 找到强连通分量的根节点
    if (low[x] == dfn[x]) {
        int now, num = 0;
        vector<int> road;       // 临时存储当前分量节点
        
        do {
            now = sta[top--];   // 弹出节点
            in[now] = 0;        // 标记出栈
            road.push_back(now);
            num += a[now];      // 累加价值
        } while (x != now);     // 直到弹出根节点
        
        // 如果是环（大小>1），设置环内所有节点答案
        if (road.size() > 1) {
            for (int node : road) {
                ans[node] = num;
            }
        }
    }
}

3. 处理非环节点

void work(int x) {
    int y = to[x];              // 下一个节点
    
    if (y == x) {               // 自环情况
        ans[x] = a[x];
        return;
    }
    
    if (!ans[y]) {              // 下一个节点未计算，递归计算
        work(y);
    }
    
    ans[x] = a[x] + ans[y];     // 自身价值 + 后续答案
}

4. 主函数流程

int main() {
    // 读入数据
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &to[i]);
    
    // 第一步：找出所有环并计算环内节点答案
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    
    // 第二步：计算剩余节点（树节点和自环节点）的答案
    for (int i = 1; i <= n; ++i) {
        if (!ans[i]) {
            work(i);
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; ++i) {
        printf("%d\n", ans[i]);
    }
    
    return 0;
}

算法原理

图的性质分析

由于每个节点只有一条出边，图的结构是：

• 环：强连通分量
• 树：指向环的链
• 自环：指向自己的节点

答案计算逻辑

1. 环内节点：一旦进入环，会遍历环中所有节点，答案为环价值和
2. 指向环的节点：答案为自身价值 + 环价值和
3. 自环节点：答案为自身价值（只能访问自己）

复杂度分析

• 时间复杂度：$O(N)$
  • Tarjan算法：每个节点访问一次
  • 记忆化搜索：每个节点处理一次
• 空间复杂度：$O(N)$
  • 存储图信息和算法状态

样例分析

对于样例：

节点价值: 5 4 3 2 1 1 1 1
出边指向: 2 3 1 1 2 7 6 8

图结构：

• 环1: 1→2→3→1（价值和=5+4+3=12）
• 环2: 6→7→6（价值和=1+1=2）
• 其他：4→1, 5→2, 8→8

计算结果：

• 节点1,2,3在环1中，答案=12
• 节点4指向环1，答案=2+12=14
• 节点5指向环1，答案=1+12=13
• 节点6,7在环2中，答案=2
• 节点8是自环，答案=1

算法优势

1. 正确性保证：基于图论的严格分析
2. 高效性：线性时间复杂度处理20万数据
3. 完整性：处理所有特殊情况（自环、单节点环等）
4. 实现简洁：算法逻辑清晰易懂

总结

本题通过结合Tarjan算法和记忆化搜索，高效解决了特殊有向图上的路径价值求和问题。算法的核心创新在于：

• 利用图的结构特性简化问题
• 分离环处理和链处理
• 使用Tarjan算法准确识别强连通分量

该解法体现了图论算法在实际问题中的应用价值，是处理此类路径相关问题的经典方法。