【bzoj3697】【采药人的路径】【点分治】
发布日期:2021-11-16 15:38:08 浏览次数:30 分类:技术文章

本文共 1251 字,大约阅读时间需要 4 分钟。

Description

采药人的药田是一个树状结构,每条路径上都种植着同种药材。

采药人以自己对药材独到的见解,对每种药材进行了分类。大致分为两类,一种是阴性的,一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的,他认为阴阳平衡是很重要的,所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的,所以他希望他选出的路径中有一个可以作为休息站的节点(不包括起点和终点),满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

Input

第1行包含一个整数N。

接下来N-1行,每行包含三个整数a_i、b_i和t_i,表示这条路上药材的类型。

Output

输出符合采药人要求的路径数目。

Sample Input

7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1

Sample Output

1

HINT

对于100%的数据,N ≤ 100,000。

题解:首先点分治是肯定的。

            我们把种类看成边权,并把0看成-1.

            对于一棵分治出来的树的子树。

            用f[i][0/1],g[i][0/1] 分别表示当前子树,当前子树之前的子树中权值为i的从子树根节点开始的路径条数.

            0/1表示路径上是否存在一个前缀和为i的点。

            那么每部分的答案就是g[0][0]*f[0][0]+sigma(g[-i][0]*f[i][1]+g[-i][1]*f[i][0]+g[-i][1]*f[i][1])

            为了好处理,我们可以把路径的权值加上n.

代码:

#include
#include
#include
#define N 100010using namespace std;int mx[N],point[N],cnt,next[N*2],deep[N],dis[N],rt,s,size[N],n,x,y,v,p[N*2],mt;long long ans,g[N*2][2],f[N*2][2];bool vis[N];struct use{int st,en,v;}e[N*2];void add(int x,int y,int v){ next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;e[cnt].v=v;}void getroot(int x,int fa){ size[x]=1;mx[x]=0; for (int i=point[x];i;i=next[i]) if (!vis[e[i].en]&&e[i].en!=fa){ getroot(e[i].en,x);size[x]+=size[e[i].en]; mx[x]=max(mx[x],size[e[i].en]); } mx[x]=max(mx[x],s-size[x]); if (mx[x]

转载地址:https://blog.csdn.net/sunshinezff/article/details/50921554 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj3142】【HNOI2013】【数列】【数学】
下一篇:【bzoj1982】【Spoj2021】【Moving Pebbles】【博弈论】

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月11日 12时27分57秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php怎么翻译数据库中的中文,javascript – 如何将翻译后的文本插入数据库php 2019-04-21
普朗克公式matlab,用MATLAB实现普朗克函数积分的快捷计算.pdf 2019-04-21
swoolec+%3c?php,PHP+Swoole并发编程的魅力 2019-04-21
php 404配置,phpcms如何配置404 2019-04-21
matlab wash矩阵产生,洗衣机净衣效能与衣损程度的关系分析 2019-04-21
php中如何调用sql server,php调用SQL SERVER 2008及以上版本的方法 2019-04-21
python多线程实现kmeans,3种方式实现python多线程并发处理 2019-04-21
matlab 变量不存在,matlab程序运行时提示变量未定义 2019-04-21
php编码函数 base58,1. Base58可逆加密 2019-04-21
oracle 在需要下列之一,Oracle存储过程中PLS-00103:出现符号“/”在需要下列之一时:(... 2019-04-21
oracle10g dblink优化,Oracle10g通过dblink访问数据异常 2019-04-21
linux安装时的iso文件,直接用ISO文件在linux上安装新系统 2019-04-21
linux修改文件权限为所有人都可以访问,Linux 笔记分享八:文件权限的设定 2019-04-21
linux中卸载ambri-servle,Kerberos 命令使用 2019-04-21
linux二进制反编译,Xori:一款来自BlackHat 2018的二进制反汇编和静态分析工具 2019-04-21
linux两台主机添加信任,Linux两台机器间添加信任,实现不用密码问,互传文件... 2019-04-21
linux 自动获取ssl证书,linux生成自验证ssl证书的具体命令和步骤 2019-04-21
linux基础命令20个,20-linux中基础命令 2019-04-21
重置网络配置 android,重置Android移动网络信号? 2019-04-21
java约瑟夫环pta上_cdoj525-猴子选大王 (约瑟夫环) 2019-04-21