为什么第10行要打标记?
查看原帖
为什么第10行要打标记?
572587
cmrhhh楼主2025/1/4 16:22

不加就WA了?

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
#define int long long
int n,a[maxn+10],ms[maxn+10],ans=0,f[maxn+10][2],fa[maxn+10];
vector<int> g[maxn+10];
int root;/*g[u]:u is hated by g*/ 
bool vis[maxn+10];
void dp(int u){
	vis[u]=1;
	f[u][0]=0;f[u][1]=ms[u];
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i];
		if(v!=root){
			dp(v);
			f[u][0]+=max(f[v][0],f[v][1]);
			f[u][1]+=f[v][0];
		}
	
	}
}
void find_circle(int x){
	root=x;
	while(!vis[root]){
		vis[root]=1;
		root=fa[root];
	}
	dp(root);
	/*force not to choose root*/
	int t=f[root][0];
	root=fa[root];
	dp(root); 
	ans+=max(t,f[root][0]);
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,v=0;i<=n;++i){
		cin>>ms[i]>>v;
		g[v].push_back(i);
		fa[i]=v;
	}
	for(int i=1;i<=n;++i)if(!vis[i]){
		find_circle(i);
	}
	cout<<ans;
	
	return 0;
}
/*
10
414757 5
141992 6
869989 9
783002 2
325736 10
40603 4
703556 6
831848 5
314650 5
293203 1

3603152
*/
2025/1/4 16:22
加载中...