首页 > 代码库 > BZOJ3697: 采药人的路径
BZOJ3697: 采药人的路径
题解：
刚开始看见，这不大水题，选出重心然后每条链看一下是不是平衡，乘法原理搞一下
码完之后居然没过样例，然后发现不一定以该店为剖分点。。。
那我们就记录一下链上两种颜色的差，然后取相反数是合法的
开心写完交上去又WA
然后发现不一定颜色整体平衡就可以找出剖分点，比如aaaabbbb。。。
这时候发现我们只要a颜色为1，b颜色为-1，然后如果从0出发走到了0那么这段是平衡的。
可是点分的时候我们是从下往上走的，那我们只要记录一下当前的权值和在上面出现过没有，出现过那么说明从这点走向根会出现平衡的一段。
然后记录就可以了。
然后交上去又WA。。。。。。
又发现有可能刚好到出发点的时候平衡，于是又特判了一下。。。
发现还是WA。。。
无奈对拍，拍了一组发现如果从0开始走到0又走到0，这样算一条合法的。。。
终于A掉了。。。语死早大家将就着看吧。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1000000+514 #define maxm 20000000+515 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next)23 #define mod 100000000724 using namespace std;25 inline int read()26 {27 int x=0,f=1;char ch=getchar();28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30 return x*f;31 }32 struct edge{int go,next,w;}e[maxn];33 int n,sum,rt,tot,cnt1,cnt2,head[maxn],s[maxn],f[maxn],g[maxn][2],d[maxn][2],v[maxn];34 ll ans;35 bool del[maxn];36 inline void insert(int x,int y,int z)37 {38 e[++tot]=(edge){y,head[x],z};head[x]=tot;39 e[++tot]=(edge){x,head[y],z};head[y]=tot;40 }41 inline void getrt(int x,int fa)42 {43 s[x]=1;f[x]=0;44 for4(i,x)if(!del[y=e[i].go]&&y!=fa)45 {46 getrt(y,x);47 s[x]+=s[y];48 f[x]=max(f[x],s[y]);49 }50 f[x]=max(f[x],sum-f[x]);51 if(f[x]<f[rt])rt=x;52 }53 inline void get(int x,int fa,int w)54 {55 d[++cnt2][0]=w;d[cnt2][1]=v[w+n];56 v[w+n]++;57 for4(i,x)if(!del[y=e[i].go]&&y!=fa)get(y,x,w+e[i].w);58 v[w+n]--;59 }60 inline void work(int x)61 {62 del[x]=1;cnt1=0;cnt2=0;63 for4(i,x)if(!del[y=e[i].go])64 {65 get(y,x,e[i].w);66 for2(j,cnt1+1,cnt2)ans+=(ll)((d[j][1]!=0)*g[-d[j][0]+n][0]+g[-d[j][0]+n][1]);67 for2(j,cnt1+1,cnt2)g[d[j][0]+n][d[j][1]!=0]++;68 cnt1=cnt2;69 }70 for1(j,cnt2){if(d[j][0]==0&&d[j][1]>1)ans++;g[d[j][0]+n][0]=g[d[j][0]+n][1]=0;}71 for4(i,x)if(!del[y=e[i].go])72 {73 sum=s[y];rt=0;74 getrt(y,0);75 work(rt);76 }77 }78 int main()79 {80 freopen("input.txt","r",stdin);81 freopen("output.txt","w",stdout);82 n=read();83 for1(i,n-1){int x=read(),y=read(),z=read();insert(x,y,z?1:-1);}84 sum=n;f[rt=0]=inf;v[n]=1;85 getrt(1,0);86 work(rt);87 cout<<ans<<endl;88 return 0;89 90 }
3697: 采药人的路径
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 71 Solved: 27
[Submit][Status]
Description
采药人的药田是一个树状结构，每条路径上都种植着同种药材。
采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。
Input
第1行包含一个整数N。
接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。
Output
输出符合采药人要求的路径数目。
Sample Input
7
l 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1
l 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。
BZOJ3697: 采药人的路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。