Submission

[PPPPPPPPPP][PPPPP][PPPPPPPP][PPPPPPPPxS]

Score: 30

User: KotatsuCat

Problemset: D.Drunk

Language: cpp

Time: 0.706 second

Submitted On: 2025-01-07 20:18:31

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;

const int mxN = 1e6+1;
pii adj[mxN];
vector<int> g[mxN];
int dist1[mxN], dist2[mxN], deg[mxN], gp[mxN];
bool vis[mxN];

void dfs(int u, int p){
	dist2[u] = 0;
	for(auto &v:g[u]){
		if(v==p || deg[v]) continue;
		dfs(v, u);
		dist2[u]=max(dist2[u], dist2[v]+adj[v].second);
	}
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n; cin >> n;
	for(int i=1;i<=n;i++) cin >> adj[i].second;
	for(int i=1;i<=n;i++) cin >> adj[i].first;
	for(int i=1;i<=n;i++){
		if(i==adj[i].first) continue;
		g[adj[i].first].emplace_back(i);
		deg[adj[i].first]++;
	}
	for(int i=1;i<=n;i++){
		if(deg[i] || vis[i]) continue;
		int u = i;
		while(!deg[u]){
			int v = adj[u].first;
			deg[v]--;
			vis[u] = true;
			u = v;
		}
	}
	fill(vis, vis+n+1, false);
	int id = 0;
	for(int i=1;i<=n;i++){
		if(vis[i] || !deg[i]) continue;
		int u = i;
		++id;
		while(!vis[u]){
			int v = adj[u].first;
			--deg[v];
			gp[u]=id;
			dist1[gp[u]]+=adj[u].second;
			vis[u] = true;
			u = v;
		}
	}
	// fill(vis, vis+n+1, false);
	for(int i=1;i<=n;i++) if(deg[i]) dfs(i, -1);
	int ans = 0;
	for(int i=1;i<=n;i++) ans = max(ans, dist1[gp[i]]+dist2[i]);
	// {
	// 	int i = 1;
	// 	cerr << "DEBUG: " << dist1[gp[i]] << " " << dist2[i] << "\n";
	// }
	cout << ans;

	return 0;
}