Submission

[-SSSSSSSSS][PPPPP][-SSSSSSS][-SSSSSSSSS]

Score: 5

User: KotatsuCat

Problemset: D.Drunk

Language: cpp

Time: 0.267 second

Submitted On: 2025-01-07 19:48:35

#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) continue;
		if(!vis[v]) 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++){
		g[adj[i].first].emplace_back(i);
		deg[adj[i].first]++;
	}
	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;
			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(!vis[i]) dfs(i, i);
	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;
}