【ZJOJ5186】【NOIP2017提高组模拟6.30】tty's home
2024-10-07 06:47:43
题目
分析
如果直接求方案数很麻烦。
但是,我们可以反过来做:先求出所有的方案数,在减去不包含的方案数。
由于所有的路径连在一起,
于是\(设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);
}
最新文章
- SQL中EXISTS的使用
- ASP.NET MVC和EF集成AngularJS开发
- ECMAScript Web APIs node.js
- sis9280触摸ic 基于rk3288 的安卓4.4的 多点触摸
- Use Dapper ORM With ASP.NET Core
- [转载]提高rails new时bundle install运行速度
- zepto源码--定义变量--学习笔记
- I-MooFest(POJ 1990)
- Swiper之初识
- GIS中相交的定义(OGC相交的定义)
- [Angular 2] Using ngrx/store and Reducers for Angular 2 Application State
- 【iOS开发之OC和JS互调】
- MDK的优化应用(转)
- java.util.concurrent.ExecutionException: org.apache.catalina.LifecycleException: Failed to start component [StandardEngine[Catalina].StandardHost[localhost].StandardContext
- 火狐开发----从头用到尾的cfx
- sqlserver2008 T_SQL篇
- Java&#160;win7或&#160;xp下配置JDK环境变量
- 细说log4j之概述
- (4.1)mysql备份还原——mysql常见故障
- springcloud配置中心客户端配置遇到的坑
热门文章
- MySQL 常用工具sysbench/fio/tpcc等测试
- 汇编语言——用DOSBox的debug查看CPU和内存 &; 用机器指令和汇编指令编程
- python学习之生成器
- 二叉平衡树AVL的插入与删除(java实现)
- [转帖]Ubuntu 18.04 server安装图形界面及realvnc远程桌面连接
- Windows2012r2 安装SQLSERVER2017 与 SQLSERVER2016 的错误提示解决KB2919355 以及 KB2919442
- python中self与__init__怎么解释能让小白弄懂?
- 在Ueditor的内容区添加一个下拉选框改变事件
- 解决Response.AddHeader中文乱码问题
- Java学习:identityHashCode和hashCode方法