「BZOJ3697」「FJ2014集训」采药人的路径

2014年9月26日8,7759

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。

题解

来自出题人hta的题解。。

本题可以考虑树的点分治。问题就变成求过根满足条件的路径数。

路径上的休息站一定是在起点到根的路径上,或者根到终点的路径上。

如何判断一条从根出发的路径是否包含休息站?只要在dfs中记录下这条路径的和x,同时用个标志数组判断这条路径是否存在前缀和为x的节点。

这样我们枚举根节点的每个子树。用f[i][0…1],g[i][0…1]分别表示前面几个子树以及当前子树和为i的路径数目,0和1用于区分路径上是否存在前缀和为i的节点。那么当前子树的贡献就是f[0][0] * g[0][0] + Σf [i][0] * g [-i][1] + f[i][1] * g[-i][0] + f[i][1] * g[-i][1],其中i的范围[-d,d],d为当前子树的深度。

 

avatar
4 Comment threads
5 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
ZXCVBNM_1ORZ+1ChenyaohzwerORZ Recent comment authors
  Subscribe  
提醒
ZXCVBNM_1
ZXCVBNM_1

Orz hzwer ,这样做为什么可以满足 “起点到休息站和休息站到终点的路径也是阴阳平衡的”这个条件???

ORZ+1
ORZ+1

orzhzw~orzhta~orzcyr~orzwwx~orzzcz~orzdkf

ORZ
ORZ

chenyao是cjy的缩写吗?

Chenyao

不是= =

Chenyao

Orz hzwer,ans+=(g [0]-1)*f [0];这里我没有太看懂,为什么要把两个前缀和为0的视为不存在有前缀和相等呢?我把g[0][0]归类到g[0] ,但是统计起来不对= =