題目描述

Z 國的騎士團是一個很有勢力的組織，幫會中匯聚了來自各地的精英。他們劫富濟貧，懲惡揚善，受到社會各界的贊揚。

最近發生了一件可怕的事情，邪惡的 Y 國發動了一場針對 Z 國的侵略戰爭。戰火綿延五百里，在和平環境中安逸了數百年的 Z 國又怎能抵擋的住 Y 國的軍隊。于是人們把所有的希望都寄托在了騎士團的身上，就像期待有一個真龍天子的降生，帶領正義打敗邪惡。

騎士團是肯定具有打敗邪惡勢力的能力的，但是騎士們互相之間往往有一些矛盾。每個騎士都有且僅有一個自己最厭惡的騎士（當然不是他自己），他是絕對不會與自己最厭惡的人一同出征的。

戰火綿延，人民生靈涂炭，組織起一個騎士軍團加入戰斗刻不容緩！國王交給了你一個艱巨的任務，從所有的騎士中選出一個騎士軍團，使得軍團內沒有矛盾的兩人（不存在一個騎士與他最痛恨的人一同被選入騎士軍團的情況），并且，使得這支騎士軍團最具有戰斗力。

為了描述戰斗力，我們將騎士按照 $1$ 至 $n$ 編號，給每名騎士一個戰斗力的估計，一個軍團的戰斗力為所有騎士的戰斗力總和。

輸入格式

第一行包含一個整數 $n$，描述騎士團的人數。

接下來 $n$ 行，每行兩個整數，按順序描述每一名騎士的戰斗力和他最痛恨的騎士。

輸出格式

應輸出一行，包含一個整數，表示你所選出的騎士軍團的戰斗力。

輸入輸出樣例 #1

輸入 #1

3
10 2
20 3
30 1

輸出 #1

30

說明/提示

數據規模與約定

對于 $30\%$ 的測試數據，滿足 $n\le 10$；

對于 $60\%$ 的測試數據，滿足 $n\le 100$；

對于 $80\%$ 的測試數據，滿足 $n\le 10^4$。

對于 $100\%$ 的測試數據，滿足 $1\le n\le 10^6$，每名騎士的戰斗力都是不大于 $10^6$ 的正整數。

solution

題目大意：基環森林中，不相鄰點的距離和的最大值
思路：

• 找到環上的某個點 u
• 以 u 和其父節點 fa[u] 為根節點樹上 dp 計算 f[i], g[i] ,即包含本節點的子樹最大和和不含本節點的子樹最大和
• 結果為 $\sum (max(g[u],g[fa[u]])$ 其中 u 為每個基環樹中環上取一個點

代碼

#include<iostream>
#include<vector>
#include "algorithm"
#include "cstring"using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 5, M = 1e9 + 7;int n, fa[N], vis[N], a[N];ll f[N], g[N];vector<int> e[N];int find_u(int u) {vis[u] = 1;return vis[fa[u]] ? u : find_u(fa[u]);
}void dp(int u, int p) {vis[u] = 1;for (int v: e[u]) {if (v == p) continue; // p 是起點，相當于斷開了起點和其fa的邊dp(v, p);f[u] += g[v];g[u] += max(f[v], g[v]);}f[u] += a[u];
}/** 1 反向建圖，形成外向基環樹* 2 找到環上一個點 u, 以 u 為根節點進行樹上 dp*      f[u]:包含本節點的最大值*      g[u]:不包含本節點的最大值* 3 以 fa[u] 為根節點進行樹上 dp*      max(g[u], g[fa])*/int main() {cin >> n;for (int i = 1; i <= n; i++) {scanf("%d%d", a + i, fa + i);// cin >> a[i] >> fa[i]; // 反向建圖，形成外向基環樹e[fa[i]].push_back(i);}ll ans = 0; for (int i = 1; i <= n; i++) {if (!vis[i]) {ll Max = 0;int u = find_u(i);dp(u, u);Max = max(Max, g[u]);memset(f, 0, sizeof f);memset(g, 0, sizeof g);dp(fa[u], fa[u]);Max = max(Max, g[fa[u]]);ans += Max;}}cout << ans << endl;return 0;
}

結果