「BZOJ3697」「FJ2014集训」采药人的路径
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
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为当前子树的深度。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt,sum,rt,mxdeep; bool vis[200005]; int t[200005],mx[100005],fa[100005],size[100005],deep[100005],dis[100005]; ll ans,g[200005][2],f[200005][2]; struct edge{int to,next,v;}e[200005];int last[100005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } void getroot(int x,int fa) { size[x]=1;mx[x]=0; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { getroot(e[i].to,x); size[x]+=size[e[i].to]; mx[x]=max(mx[x],size[e[i].to]); } mx[x]=max(mx[x],sum-size[x]); if(mx[x]<mx[rt])rt=x; } void dfs(int x,int fa) { mxdeep=max(mxdeep,deep[x]); if(t[dis[x]])f[dis[x]][1]++; else f[dis[x]][0]++; t[dis[x]]++; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa&&!vis[e[i].to]) { deep[e[i].to]=deep[x]+1; dis[e[i].to]=dis[x]+e[i].v; dfs(e[i].to,x); } t[dis[x]]--; } void cal(int x) { int mx=0; vis[x]=1;g[n][0]=1; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { dis[e[i].to]=n+e[i].v; deep[e[i].to]=1; mxdeep=1;dfs(e[i].to,0);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][1]+g[n-j][0]*f[n+j][1]+g[n-j][1]*f[n+j][0]; for(int j=n-mxdeep;j<=n+mxdeep;j++) { g[j][0]+=f[j][0]; g[j][1]+=f[j][1]; f[j][0]=f[j][1]=0; } } for(int i=n-mx;i<=n+mx;i++) g[i][0]=g[i][1]=0; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]) { sum=size[e[i].to]; rt=0; getroot(e[i].to,0); cal(rt); } } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); if(!w)w=-1; insert(u,v,w); } sum=mx[0]=n; getroot(1,0); cal(rt); printf("%lld",ans); return 0; } |
计数器 9854084
OI 课件=>
OI 课件=>
Orz hzwer ,这样做为什么可以满足 “起点到休息站和休息站到终点的路径也是阴阳平衡的”这个条件？？？
orzhzw~orzhta~orzcyr~orzwwx~orzzcz~orzdkf
chenyao是cjy的缩写吗？
卧槽
别装了，就是cjy的缩写
不是= =
Orz hzwer,ans+=(g
[0]-1)*f 
[0];这里我没有太看懂，为什么要把两个前缀和为0的视为不存在有前缀和相等呢？我把g[0][0]归类到g[0] 
，但是统计起来不对= =
没听懂。。。
无视我，是我傻逼了，忘了统计以当前树根为路径端点的点了