Submission #490543

---

Source Code Expand

#include <bits/stdc++.h>

#define MAX_N (100000)
#define MAX_M (100000)


using namespace std;

vector<int> G[MAX_N];
vector<pair<int, int> > bridge;
int ord[MAX_N], low[MAX_N];
int w[MAX_N];
bool vis[MAX_N];

void dfs(int v, int p, int &k)
{
	vis[v] = true;

	ord[v] = k++;
	low[v] = ord[v];

	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]]){
			dfs(G[v][i], v, k);
			low[v] = min(low[v], low[G[v][i]]);
			if (ord[v] < low[G[v][i]]) bridge.push_back(make_pair(v, G[v][i]));
		}
		else if (G[v][i] != p){
			low[v] = min(low[v], ord[G[v][i]]);
		}
	}
}

int par[MAX_N];

int find(int x)
{
	return (par[x] >= 0 ? par[x] = find(par[x]) : x);
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (-par[x] < -par[y]) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

int nw[MAX_N];
int nSize[MAX_N];
vector<int> nG[MAX_N];
//int dp[MAX_N];
int dp1[MAX_N];
int dp2[MAX_N];	// return

/*
int getMax(int v, int p)
{
	if (dp[v] >= 0) return (dp[v]);

	int res = 0;
	for (int i = 0; i < nG[v].size(); i++){
		if (nG[v][i] != p) res = max(res, getMax(nG[v][i], v));
	}

	return (dp[v] = res + nw[v]);
}
*/

void getMax2(int v, int p){
	if(dp1[v] >= 0){ return; }
	
	if(p == -1 && nG[v].empty()){
		dp1[v] = dp2[v] = nw[v];
		return;
	}
	if(p != -1 && nG[v].size() <= 1){
		if(nSize[v] == 1){
			dp1[v] = nw[v];
			dp2[v] = 0;
		}
		else{
			dp1[v] = dp2[v] = nw[v];
		}
		return;
	}

	int sum2 = 0;
	for(int i = 0; i < nG[v].size(); ++i){
		int t = nG[v][i];
		if(t == p){ continue; }
		getMax2(t, v);
		sum2 += dp2[t];
	}

	int res1 = 0;
	for(int i = 0; i < nG[v].size(); ++i){
		int t = nG[v][i];
		if(t == p){ continue; }
		res1 = max(res1, sum2 - dp2[t] + dp1[t]);
	}
	res1 += nw[v];

	int res2 = sum2;
	if(res2 != 0 || nSize[v] > 1){
		res2 += nw[v];
	}

	dp1[v] = res1;
	dp2[v] = res2;
}


int main()
{
	int N, M;

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) scanf("%d", w + i);

	for (int i = 0; i < M; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		G[--x].push_back(--y);
		G[y].push_back(x);
	}

	int k = 0;

	dfs(0, -1, k);

	for (int i = 0; i < bridge.size(); i++){
		{
			auto &v = G[bridge[i].first];
			v.erase(find(v.begin(), v.end(), bridge[i].second));
		}
		{
			auto &v = G[bridge[i].second];
			v.erase(find(v.begin(), v.end(), bridge[i].first));
		}
	}

	memset(par, -1, sizeof(par));

	for (int i = 0; i < N; i++){
		for (int j = 0; j < G[i].size(); j++){
			merge(i, G[i][j]);
		}
	}

	for (int i = 0; i < N; i++){
		nw[find(i)] += w[i];
	}

	for (int i = 0; i < N; i++){
		nSize[find(i)] = -par[find(i)];
	}

	for (int i = 0; i < bridge.size(); i++){
		bridge[i].first = find(bridge[i].first);
		bridge[i].second = find(bridge[i].second);
		nG[bridge[i].first].push_back(bridge[i].second);
		nG[bridge[i].second].push_back(bridge[i].first);
	}

//	memset(dp, -1, sizeof(dp));
	memset(dp1, -1, sizeof dp1);
	memset(dp2, -1, sizeof dp2);

	int aaa = find(0);
	getMax2(aaa, -1);
	int ans = max(dp1[aaa], dp2[aaa]);
	printf("%d\n", ans);

//	printf("%d\n", getMax(find(0), -1));

	return (0);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:120:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
                        ^
./Main.cpp:122:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) scanf("%d", w + i);
                                                ^
./Main.cpp:126:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
                         ^

Judge Result