3697: 采药人的路径

admin管理员组

文章数量:1516870

3697: 采药人的路径

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为当前子树的深度。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<algorithm>
  7 #include<string>
  8 #include<map>
  9 #include<queue>
 10 #include<vector>
 11 #include<set>
 12 #define inf 1000000000
 13 #define maxn 100005
 14 #define maxm 200005
 15 #define eps 1e-10
 16 #define ll long long
 17 #define for0(i,n) for(int i=0;i<=(n);i++)
 18 #define for1(i,n) for(int i=1;i<=(n);i++)
 19 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 20 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 21 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
 22 using namespace std;
 23 int read(){
 24     int x=0,f=1;char ch=getchar();
 25     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 26     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 27     return x*f;
 28 }
 29 int n,tot,sum,rt,mxdeep;
 30 bool vis[maxm];
 31 int t[maxm],mx[maxn],fa[maxn],size[maxn],deep[maxn],d[maxn],head[maxn];
 32 ll ans,g[maxm][2],f[maxm][2];
 33 struct edge{
 34     int go,next,w;
 35 }e[maxm];
 36 void insert(int u,int v,int w){
 37     e[++tot].go=v;e[tot].next=head[u];head[u]=tot;e[tot].w=w;
 38     e[++tot].go=u;e[tot].next=head[v];head[v]=tot;e[tot].w=w;
 39 }
 40 void getroot(int x,int fa){
 41     size[x]=1;mx[x]=0;
 42     for4(i,x){
 43         if(y!=fa&&!vis[y]){
 44             getroot(y,x);
 45             size[x]+=size[y];
 46             mx[x]=max(mx[x],size[y]);
 47         }
 48     }
 49     mx[x]=max(mx[x],sum-size[x]);
 50     if(mx[x]<mx[rt])rt=x;
 51 }
 52 void dfs(int x,int fa){
 53     mxdeep=max(mxdeep,deep[x]);
 54     if(t[d[x]])f[d[x]][1]++;
 55     else f[d[x]][0]++;
 56     t[d[x]]++;
 57     for4(i,x){
 58         if(y!=fa&&!vis[y]){
 59             deep[y]=deep[x]+1;
 60             d[y]=d[x]+e[i].w;
 61             dfs(y,x);
 62         }
 63     }
 64     t[d[x]]--;
 65 }
 66 void cal(int x){
 67     int mx=0;
 68     vis[x]=1;g[n][0]=1;
 69     for4(i,x){
 70         if(!vis[y]){
 71             d[y]=n+e[i].w;
 72             deep[y]=1;
 73             mxdeep=1;dfs(y,0);mx=max(mx,mxdeep);
 74             ans+=(g[n][0]-1)*f[n][0];
 75             for(int j=-mxdeep;j<=mxdeep;j++)
 76                 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];
 77             for(int j=n-mxdeep;j<=n+mxdeep;j++){
 78                 g[j][0]+=f[j][0];
 79                 g[j][1]+=f[j][1];
 80                 f[j][0]=f[j][1]=0;
 81             }
 82         }
 83     }
 84     for(int i=n-mx;i<=n+mx;i++)g[i][0]=g[i][1]=0;
 85     for4(i,x){
 86         if(!vis[y]){
 87             sum=size[y];
 88             rt=0;
 89             getroot(y,0);
 90             cal(rt);
 91         }
 92     }
 93 }
 94 int main(){
 95     //freopen("input.txt","r",stdin);
 96     //freopen("output.txt","w",stdout);
 97     n=read();
 98     for1(i,n-1){
 99         int u=read(),v=read(),w=read();
100         if(!w)w=-1;
101         insert(u,v,w);
102     }
103     sum=mx[0]=n;
104     getroot(1,0);
105     cal(rt);
106     printf("%lld",ans);
107     return 0;
108 }

View Code

 

转载于:.html

本文标签： 3697 采药人的路径