3697: 采药人的路径
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1723 Solved: 603[][][]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。
今天做了昨天的一道点分治的题 细节真的可以说是很多了...
看到这道题 树上路径 然后就可以想到点分治 然后这道题就是根据乘法原理组合路径求答案的
然后对于阳性药他的权值是1 然后阴性的是-1 所以说一条阴阳平衡的路径路径和为0
由题可知休息站到终点和起点的路径和为0 那么很显然整条路径也一定是合法的
所以我们就只需要找到合法的路径就可以了
以下题解摘自 http://hzwer.com/4526.html
路径上的休息站一定是在起点到根的路径上，或者根到终点的路径上。
如何判断一条从根出发的路径是否包含休息站？只要在dfs中记录下这条路径的和x，同时用个标志数组判断这条路径是否存在前缀和为x的节点。
这样我们枚举根节点的每个子树。用g[i][0 / 1]，f[i][0 / 1]分别表示前面几个子树以及当前子树和为i的路径数目，
0和1用于区分路径上是否存在前缀和为i的节点。
那么当前子树的贡献就是$f[0][0] * g[0][0] + \sum (f [i][0] * g [-i][1] + f[i][1] * g[-i][0] + f[i][1] * g[-i][1])$
其中i的范围[-d,d]，d为当前子树的深度。 所以就直接给所有值都加上n就可以了 这样子下标就不会超界
代码
#includeusing namespace std;typedef long long ll;const int oo = 1e7;const int N = 1e5 + 5;int n,head[N],tov[2 * N],nex[2 * N],val[2 * N],sum;int tot,size[N],root,mxdeep,MX,deep[N],dis[N],t[N];ll f[2 * N][2],g[2 * N][2],ans;bool vis[2 * N];void add(int u,int v,int w) { tot ++; tov[tot] = v; nex[tot] = head[u]; val[tot] = w; head[u] = tot;}void find_root(int u,int fa) { size[u] = 1; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(v == fa || vis[v]) continue; find_root(v,u); size[u] += size[v]; } int cmp = max(sum - size[u],size[u]); if(cmp < MX) { MX = cmp; root = u; }}void dfs(int u,int fa,int dd) { mxdeep = max(deep[u],mxdeep); dis[u] = dd; if(t[dis[u]]) f[dis[u]][1] ++; else f[dis[u]][0] ++; t[dis[u]] ++; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(vis[v] || v == fa) continue; deep[v] = deep[u] + 1; dfs(v,u,dd + val[i]); } t[dis[u]] -- ;} void divide(int u) { vis[u] = true; g[n][0] = 1; deep[u] = 0; int mx = 0; for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(vis[v]) continue; deep[v] = 1; mxdeep = 1; dfs(v,u,n + val[i]); mx = max(mx,mxdeep); ans += (g[n][0] - 1) * f[n][0]; for(int j = -mxdeep;j <= mxdeep;j ++) { ans += g[n - j][1] * f[n + j][0] + g[n - j][0] * f[n + j][1] + g[n - j][1] * f[n + j][1]; } for(int j = -mxdeep;j <= mxdeep;j ++) { g[n - j][0] += f[n - j][0]; g[n - j][1] += f[n - j][1]; f[n - j][0] = f[n - j][1] = 0; } } for(int j = -mx;j <= mx;j ++) { g[n - j][0] = g[n - j][1] = 0; } for(int i = head[u];i;i = nex[i]) { int v = tov[i]; if(vis[v]) continue; sum = size[v]; MX = oo; find_root(v,u); divide(root); }}int main( ) { scanf("%d",& n); for(int i = 1;i < n;i ++) { int u,v,w; scanf("%d%d%d",& u,& v,& w); if(! w) w = -1; add(u,v,w); add(v,u,w); } MX = oo; sum = n; find_root(1,0); divide(root); printf("%lld",ans);}