【0】做题心得 - 2025 NOIP #67 - T2 / 题解：P13118 [GCJ 2019 #2] Contransmutation【Tarjan】【图论】【缩点】【动态规划】

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
const ll P=1e9+7;
ll d[N]; bool z[N];
int n,a[N],cnt[N],deg[N];
int id[N],low[N],ic;
int sid[N],stk[N],top,sd,sz[N];
vector<int>e[N],g[N],nd[N];
bool vis[N];
void tarjan(int p){
	stk[++top]=p;
	id[p]=low[p]=++ic;
	for(auto v:e[p]){
		if(!id[v]){
			tarjan(v);
			low[p]=min(low[p],low[v]);
		}else if(!sid[v])
			low[p]=min(low[p],id[v]);
	}
	if(low[p]==id[p]){
		++sd;
		int q=stk[top];
		do{
			q=stk[top], --top;
			sid[q]=sd;
			sz[sd]++;
			d[sd]=(d[sd]+a[q])%P;
			z[sd]=z[sd]|bool(a[q]);
			nd[sd].push_back(q);
		}while(p!=q);
	}
	return;
}
queue<int>q;
int main(){
	freopen("virus.in","r",stdin);
	freopen("virus.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int u,v;
		cin>>u>>v;
		e[i].push_back(u);
		e[i].push_back(v);
	}
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)if(!id[i])
		tarjan(i);
	for(int i=1;i<=n;i++)for(auto v:e[i])
		if(sid[i]==sid[v]) cnt[sid[i]]++;
		else g[sid[i]].push_back(sid[v]), deg[sid[v]]++;
	for(int i=1;i<=sd;i++)
		if(!deg[i]) q.push(i);
	while(q.size()){
		int p=q.front();
		q.pop();
		if(cnt[p]>sz[p]&&z[p]) d[p]=-1;
		for(auto v:g[p]){
			z[v]=z[v]|z[p];
			if(d[p]==-1||d[v]==-1||(cnt[p]==sz[p]&&z[p])) d[v]=-1;
			else d[v]=(d[v]+d[p])%P;
			if(!(--deg[v])) q.push(v);
		}
	}
	for(int i=1;i<=n;i++)
		cout<<d[sid[i]]<<" ";
	return 0;
}