「bsoj1453」食物链 - 树形动规

题目大意

    PCY 最近在努力地学习生物。看到食物链这一节的时候，他迷茫了。
    生态系统中的生物种类众多，亦于生态系统分别扮演着不同的角色，但根据它们在能量和物质中所引起的作用，可以被分类为生产者、消费者和分解者三个类别。最底层是“生产者”，是以阳光来行使光合作用，自行用水和二氧化碳等无机物合成有机物的绿色植物；再上层是各级“消费者”，要依赖生产者供应物质和能量；当消费者死亡以后，“分解者”会以他们的尸体为食物。
    生物必修二曾写道，“两个营养级之间的能量传递效率为$10\%\rightarrow20\%$”。
    PCY说，“那些错综复杂的食物网我根本看不清楚”，于是我们将问题简化，每一个物种只存在唯一一个的捕食者（形成捕食关系），给出这些捕食关系，和每个物种所拥有的能量。求出整个食物网中食物链的数量和处在最高营养级的物种的能量。（某一物种的能量=摄入食物的能量*传递效率+自身能量），不考虑能量损耗，为了避免精度误差，能量效率按均为整数计算。也就是说，一个物种被吃了以后他的能量就成了他的数倍了。

---

题目分析

简单的树形动规，需要注意手工栈+卡常数。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
namespace FastIO {
	const int L=1<<15;
	char buf[L],*S,*T;
	char getchar() {
		if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
		return *S++;
	}
	LL Get_Int(){
		LL res=0,bj=1;char c=getchar();
		while(!isdigit(c)){if(c=='-')bj=-1;c=getchar();}
		while(isdigit(c)){res=res*10+c-'0';c=getchar();}
		return res*bj;
	}
}
using FastIO::Get_Int;
const int maxn=2000005;
const LL mod=32416190071;
int n,vst[maxn],ans=0;
LL f[maxn];
struct Edge {
	int from,to,dist;
};
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {
		x,y,v
	});
}
void Dfs(int Now) {
	for(auto& e:edges[Now]) {
		int Next=e.to;
		Dfs(Next);
		f[Now]=(f[Now]+f[Next]*e.dist)%mod;
	}
}
int main() {
	int size=100<<20; //40M
	__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
	n=Get_Int();
	for(int i=1; i<n; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		vst[y]=1;
		AddEdge(x,y,v);
	}
	int root;
	for(int i=1; i<=n; i++) {
		f[i]=Get_Int()%mod;
		if(!edges[i].size())ans++;
		if(!vst[i])root=i;
	}
	Dfs(root);
	printf("%d\n%lld\n",ans,f[root]);
	exit(0);
}