【ZJOJ5186】【NOIP2017提高组模拟6.30】tty's home

题目

分析

如果直接求方案数很麻烦。

但是，我们可以反过来做：先求出所有的方案数，在减去不包含的方案数。

由于所有的路径连在一起，

于是\(设f[i]表示以i为根的子树中，连接到i的方案数\)

则\(f[i]=f[son]+(f[i]+1)\)表示从子树son分别到i和i其他儿子的子树的路径方案数。

由于每棵子树互不影响，\(ans=\sum_{i=1}^nf[i]\)

对于不包含的，就是当son为最大值就不转移到父亲上，且当i为最大值不加入ans。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const long long mo=998244353;

const long long N=100005;

using namespace std;

struct arr

{

	int v,p;

}b[N];

long long f[N],n,last[N*2],to[N*2],next[N*2],tot,ans,size[N],ans1;

bool bz[N];

bool cmp(arr x,arr y)

{

	return x.v>y.v;

}

void bj(int x,int y)

{

	next[++tot]=last[x];

	last[x]=tot;

	to[tot]=y;

}

void dg(int x,int fa)

{

	for(int i=last[x];i;i=next[i])

	{

		int j=to[i];

		if(j!=fa) dg(j,x),(f[x]+=f[j]+f[x]*f[j]%mo)%=mo;

	}

	(ans+=++f[x])%=mo;

}

void dg1(int x,int fa)

{

	for(int i=last[x];i;i=next[i])

	{

		int j=to[i];

		if(j!=fa)

		{

			dg1(j,x);

			if(!bz[j]) (f[x]+=f[j]+f[x]*f[j]%mo)%=mo;

		}

	}

	if(!bz[x]) (ans1+=++f[x])%=mo;

}

int main()

{

	scanf("%lld",&n);

	for(int i=1;i<=n;i++) scanf("%d",&b[i].v),b[i].p=i;

	for(int i=1,x,y;i<=n-1;i++) scanf("%d%d",&x,&y),bj(x,y),bj(y,x);

	sort(b+1,b+1+n,cmp);

	bz[b[1].p]=true;

	for(int i=2;i<=n;i++)

		if(b[i].v==b[i-1].v) bz[b[i].p]=true;

		else break;

	dg(1,0);

	memset(f,0,sizeof(f));

	dg1(1,0);

	printf("%lld",(ans-ans1+2*mo)%mo);

}