Codeforces - E. Tourism

E. Tourism
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Alex decided to go on a touristic trip over the country.
For simplicity let’s assume that the country has n cities and m bidirectional roads connecting them. Alex lives in city s and initially located in it. To compare different cities Alex assigned each city a score wi which is as high as interesting city seems to Alex.
Alex believes that his trip will be interesting only if he will not use any road twice in a row. That is if Alex came to city v from city u, he may choose as the next city in the trip any city connected with v by the road, except for the city u.
Your task is to help Alex plan his city in a way that maximizes total score over all cities he visited. Note that for each city its score is counted at most once, even if Alex been there several times during his trip.
Input First line of input contains two integers n and m, (1≤n≤2⋅105, 0≤m≤2⋅105) which are numbers of cities and roads in the country.
Second line contains n integers w1,w2,…,wn (0≤wi≤109) which are scores of all cities.
The following m lines contain description of the roads. Each of these m lines contains two integers u and v (1≤u,v≤n) which are cities connected by this road.
It is guaranteed that there is at most one direct road between any two cities, no city is connected to itself by the road and, finally, it is possible to go from any city to any other one using only roads.
The last line contains single integer s (1≤s≤n), which is the number of the initial city.
Output Output single integer which is the maximum possible sum of scores of visited cities.
Examples inputCopy 5 7 2 2 8 6 9 1 2 1 3 2 4 3 2 4 5 2 5 1 5 2 outputCopy 27 inputCopy 10 12 1 7 1 9 3 3 6 30 1 10 1 2 1 3 3 5 5 7 2 3 5 4 6 9 4 6 3 7 6 8 9 4 9 10 6 outputCopy 61
사이드 더블 + 트리 dp
먼저 축소하는 것은 매우 뚜렷하다. 왜냐하면 한 변의 쌍연통 분량 중 하나는 마음대로 갈 수 있기 때문이다.
그 후에 나무가 되고 어떤 점은 돌아올 수 있고 어떤 점은 돌아올 수 없다. 어떤 것은 블록의 개수에 따라 2보다 크면 돌아올 수 있다.
그럼 우리 계속 줄여요. 어떻게 줄여요?
어떤 것은 바로 돌아올 수 있기 때문에 우리가 직접 그의 아버지에게 권한을 주면 되잖아. 그리고 그의 권한 상황을 아버지의 사이즈를 갱신하면 되잖아.
이후에 다시 한 번 dfs를 하면 돌아올지 안 돌아올지 고려할 필요가 없다. 모두 돌아올 수 없는 것으로 간주한다. 왜냐하면 돌아오는 것은 이미 줄어들었기 때문이다.
AC 코드:

#pragma GCC optimize(2)
#include
#define int long long
using namespace std;
const int N=2e5+10,M=4e5+10;
int n,m,dfn[N],low[N],col[N],sum[N],brige[M],w[N],vis[N],co,cnt,s,dp[N],num[N];
int head[N],nex[M],to[M],tot=1;
stack<int> st;	vector<int> v[N];
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void Tarjan(int x){
	dfn[x]=low[x]=++cnt; vis[x]=1;	st.push(x);
	for(int i=head[x];i;i=nex[i]){
		if(brige[i])	continue;	brige[i]=brige[i^1]=1;
		if(!dfn[to[i]]){
			Tarjan(to[i]);	low[x]=min(low[x],low[to[i]]);
		}else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]);
	}
	if(low[x]==dfn[x]){
		int u; co++;
		do{
			u=st.top();	vis[u]=0;	st.pop();	col[u]=co; sum[co]+=w[u]; num[co]++;
		}while(u!=x);
	}
}
void dfs(int x,int fa){ 
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i];
		if(to==fa)	continue;
		dfs(to,x);
		if(num[to]>=2){
			sum[x]+=sum[to]; sum[to]=0; num[x]+=num[to];
		}
	}
}
void dfs1(int x,int fa){
	dp[x]=sum[x]; int t=0;
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i];
		if(to==fa)	 continue;
		dfs1(to,x);	t=max(t,dp[to]);
	}
	dp[x]+=t;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%lld",&w[i]);
	for(int i=1,a,b;i<=m;i++)	scanf("%lld %lld",&a,&b),add(a,b),add(b,a);
	for(int i=1;i<=n;i++)	if(!dfn[i])	Tarjan(i);
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nex[j]){
			if(col[i]!=col[to[j]])	v[col[i]].push_back(col[to[j]]);
		}
	}
	cin>>s;	dfs(col[s],-1); dfs1(col[s],-1);	cout<<dp[col[s]]<<endl;
	return 0;
}