soj 2013年 Nanjing Slection

soj 2013年 Nanjing Slection

这样加边比STL快!

不明白为什么要+mod

 #include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define M(a,b) memset(a,b,sizeof(a))
typedef long long LL;
using namespace std; const LL mod = ;
int N,M;
int dp[][];
int tot[]; struct node
{
int t,nxt;
}edge[*];
int headline[];
int E;
void add(int f,int t)
{
E++;
edge[E].t = t;
edge[E].nxt = headline[f];
headline[f] = E;
} void dfs(int u, int fa)
{
for(int i = headline[u];i != -;i = edge[i].nxt)
{
int t = edge[i].t;;
if(t!=fa)
{
dfs(t,u);
for(int j = ;j<=M;j++)
{
if(tot[t]-dp[t][j]<)
dp[u][j] = ((LL)dp[u][j]*(tot[t]-dp[t][j]+mod)%mod)%mod;
else
dp[u][j] = ((LL)dp[u][j]*(tot[t]-dp[t][j])%mod)%mod;
}
}
}
for(int i = ;i<=M;i++)
{
tot[u] = (tot[u]+dp[u][i])%mod;
}
return;
} int main()
{
while(scanf("%d%d",&N,&M)==)
{
int t;
M(dp,);
M(headline,-);
M(tot,);
E=;
for(int i = ;i<=N;i++)
{
scanf("%d",&t);
int a;
for(int j = ;j<t;j++) {scanf("%d",&a);dp[i][a]=;}
}
int u,v;
for(int i = ;i<N-;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(,);
printf("%d\n",tot[]%mod);
}
return ;
}
上一篇:浏览器兼容的css hack


下一篇:设计模式之(二)Adapter模式