3697: 采药人的路径
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1540 Solved: 526
[Submit][Status][Discuss]
Description
采药人的药田是一个树状结构，每条路径上都种植着同种药材。
采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。
Input
第1行包含一个整数N。
接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。
Output
输出符合采药人要求的路径数目。
Sample Input
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1
Sample Output
HINT
对于100%的数据，N ≤ 100,000。
分析：这是一道很难的题，不光是在思维上，代码也有许多地方容易写错.
将边权变一下：0变成-1,1变成0. 选取一个点当作根，对每个点维护一个点权，表示从这个点到根的边权和. 题目就变成了：求路径，使得这个路径两个端点到路径中的某一个点的边权和为0.点权和对于维护这么一个东西有用.
路径计数问题通常采用点分治的方法.选取的根恰好就是每次分治的重心. 常规的点分治题的做法是先统计所有经过根的路径，然后统计经过根两端点在同一棵子树内的路径.这种方法适用于能够把数据放在一起处理的题. 这道题显然不行......
利用树形dp的思想：在解一类树形dp问题的时候，遇到多叉树常常把它看做二叉树. 例如如果处理到第i棵子树，那么可以理解为它有两棵子树：1.前i-1棵子树 2.第i棵子树. 每次先在这两棵子树中查询答案，再把第i棵子树合并到前i-1棵子树中去，这是一种很常见的思路.
对于这道题而言也是一样的.用一个数组f表示前i棵子树的答案，g表示第i棵子树的答案.统计完答案后就把g累加到f身上. 处理完所有的子树后就清空f,继续找重心dfs下去.
怎么统计答案呢？
考虑4个点，其中u和u'的点权是一样的，v和v'的点权是一样的，u和v的点权是相反数.那么 u'到v，u到v',u到v都是合法的路径. 这里并不关心它们具体的点权是多少，只关注每个点在根节点到它的路径上有没有点权和它一样的点,并且点权是否是相反数.
如果当前枚举到了第j棵子树，令f[i][0/1]表示前j-1棵子树中，有多少个点的点权是i,并且根到它的路径上没有/有和它点值一样的点. g[i][0/1]则表示当前第j棵子树的. ans += f[i][1] * g[-i][0] + f[i][0] * g[-i][1] + f[i][1] * g[-i][1].
一般的f[i][0] * g[-i][0]是不能统计进入答案的.但是当i = 0的时候是可以的. g[0][1]也要统计进入答案,这是由于两个0和根的0在一起就组合成一条合法的路径.这样所有合法的路径讨论完了.
细节比较多：
1.-i有可能是负数，怎么办呢？ 整体偏移一下就好了. i 变成 maxn + i. 这样的话数组就必须开两倍大. 这里特别容易错.
2.每次dfs只统计一条路径，记得清空.
3.每次找重心F数组要清零.
这道题目主要就是点分治题目的一种比较巧妙的处理方法，分类讨论要考虑清楚所有情况,注意一些细节. 以后需要多打几遍复习复习啊.
#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const ll maxn = 100010; ll n,head[maxn],to[maxn * 2],nextt[maxn * 2],w[maxn * 2],tot = 1; ll sizee[maxn],F[maxn],sum,root,f[maxn * 2][2],g[maxn * 2][2],ans; ll maxx,maxxx,dep[maxn],flag[maxn * 2],vis[maxn]; void add(ll x,ll y,ll z) { w[tot] = z; to[tot] = y; nextt[tot] = head[x]; head[x] = tot++; } void findroot(ll u,ll fa) { sizee[u] = 1; F[u] = 0; for (ll i = head[u]; i; i = nextt[i]) { ll v = to[i]; if (v == fa || vis[v]) continue; findroot(v,u); sizee[u] += sizee[v]; F[u] = max(F[u],sizee[v]); } F[u] = max(F[u],sum - sizee[u]); if (F[u] < F[root]) root = u; } void dfs(ll u,ll fa) { maxx = max(maxx,abs(dep[u])); if (flag[dep[u] + maxn]) g[dep[u] + maxn][1]++; else g[dep[u] + maxn][0]++; flag[dep[u] + maxn]++; for (ll i = head[u]; i; i = nextt[i]) { ll v = to[i]; if (vis[v] || v == fa) continue; dep[v] = dep[u] + w[i]; dfs(v,u); } flag[dep[u] + maxn]--; } void solve(ll u) { vis[u] = 1; maxxx = 0; for (ll i = head[u]; i; i = nextt[i]) { ll v = to[i]; if (vis[v]) continue; dep[v] = w[i]; maxx = 0; dfs(v,u); maxxx = max(maxxx,maxx); for (ll j = maxn - maxx; j <= maxn + maxx; j++) { ans += f[2 * maxn - j][0] * g[j][1]; ans += f[2 * maxn - j][1] * g[j][0]; ans += f[2 * maxn - j][1] * g[j][1]; } ans += f[maxn][0] * g[maxn][0]; ans += g[maxn][1]; for (ll j = maxn - maxx; j <= maxn + maxx; j++) { f[j][0] += g[j][0]; f[j][1] += g[j][1]; g[j][0] = g[j][1] = 0; } } for (ll i = maxn - maxxx; i <= maxn + maxxx; i++) f[i][0] = f[i][1] = 0; for (ll i = head[u]; i; i = nextt[i]) { ll v = to[i]; if (vis[v]) continue; sum = F[0] = sizee[v]; findroot(v,root = 0); solve(root); } } int main() { scanf("%lld",&n); for (int i = 1; i < n; i++) { ll x,y,z; scanf("%lld%lld%lld",&x,&y,&z); z = 2 * z - 1; add(x,y,z); add(y,x,z); } F[0] = sum = n; findroot(1,0); solve(root); printf("%lld ",ans); return 0; }