android开发分享中石油训练赛 – Flow Finder(树上模拟)

题目链接：点击查看

题目大意：给出一棵树，模拟网络流的过程，每个节点代表的是通过该节点的流量，虚拟源点连向每个叶子节点，根节点作为超级汇点，每条边的流向是流向其父节点，有一些节点的流量没有给出，现在问是否存在着唯一的一种赋值方案，使得每个节点的赋值合法且唯一

题目分析：因为源点与叶子节点相连，所以我们的当务之急是需要将所有的叶子节点进行合法的赋值，然后 dfs 自底向上检查一下每个节点是否合法且唯一即可，那么我们该如何给叶子节点赋值呢

因为整棵树的每个节点都是一个互相限制的过程，同理叶子节点也会被其祖先节点的流量所限制，所以我们在给叶子节点赋值时，并不关心那些流量未知的节点，对于每个叶子结点 i 只需要记录一下 fa[ i ] 代表的是 i 的第一个已经有确定流量的祖先节点，根据这个祖先的流量来判断能否给当前叶子节点赋值即可

代码：
 

#pragma GCC optimize(2) #pragma GCC optimize("Ofast","inline","-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;       typedef long long LL;       typedef unsigned long long ull;       const int inf=0x3f3f3f3f;     const int N=3e5+100;  vector<int>node1[N],node2[N];  int fa[N];  LL val[N],sub[N];//sub数组用来实时每个点的流量  void dfs1(int u) { 	for(auto v:node1[u]) 	{ 		if(val[u]) 			fa[v]=u; 		else 			fa[v]=fa[u]; 		dfs1(v); 	} }  void dfs2(int u) { 	LL temp=val[u]; 	if(node1[u].size()) 		val[u]=0; 	for(auto v:node1[u]) 	{ 		dfs2(v); 		val[u]+=val[v]; 	} 	if(val[u]==0||temp>0&&val[u]!=temp) 	{ 		puts("impossible"); 		exit(0); 	} }  int main() { #ifndef ONLINE_JUDGE //  freopen("data.in.txt","r",stdin); //  freopen("data.out.txt","w",stdout); #endif //  ios::sync_with_stdio(false); 	int n; 	scanf("%d",&n); 	for(int i=2;i<=n;i++) 	{ 		int fa; 		scanf("%d",&fa); 		node1[fa].push_back(i); 	} 	for(int i=1;i<=n;i++) 	{ 		scanf("%lld",val+i); 		sub[i]=val[i]; 	} 	dfs1(1); 	for(int i=1;i<=n;i++) 	{ 		sub[fa[i]]-=val[i];//更新一下每个节点的流量 		if(node1[i].empty()&&!val[i])//未赋值的叶子结点  			node2[fa[i]].push_back(i); 	} 	for(int i=1;i<=n;i++) 		if(node2[i].size())//有流量的节点  		{ 			if(node2[i].size()==1)//如果只有一个叶子节点，那么赋值为sub[i] 				val[node2[i].front()]=sub[i]; 			else if(node2[i].size()==sub[i])//如果有sub[i]个叶子结点，每个节点赋值为1 			{ 				for(auto v:node2[i]) 					val[v]=1; 			} 		} 	dfs2(1);//自底向上检查 	for(int i=1;i<=n;i++) 		printf("%lldn",val[i]);                   return 0; }