[BZOJ3697]采药人的路径（点分治）

2019-11-08 19:48:20

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

点分治裸题（笑黄学长的题解看不懂啊。。。自己yy了一种做法果然蠢到爆炸

将边权看成1和-1，那么合法的路径即为路径权值和为0，并且从中间分开两段和都是0 如果从路径的一个起点开始做前缀和的话，要求终点的权为0且中间点的权出现过0 进行点分治，每一次对所有的点做以当前根为起点的前缀和，然后每一个点都得到了一个点权要将这些点两两组合使得整条路径合法首先显然如果两个点权相加为0才是合法的匹配如果当前点到根的路径中存在点和这个点的点权相等，那么这条路径已经单独存在休息站，将这个点标记然后分类讨论如果当前点权为0，如果没有标记，那么可以和其它任意的0匹配；如果有标记，那么不光可以和其它任意的0匹配，还可以自己到根算一条路径如果当前点权不为0且没有标记，那么只能和有标记的匹配如果当前点权不为0且有标记，那么可以和其它任意合法的匹配用数组记录权为i的个数然后计算就行了时间复杂度O(nlogn∗一坨常数) $O(nlogn*一坨常数)$

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define LL long long#define N 100005#define base 100000int n,x,y,z,sum,root,cs,cn;int tot,point[N],nxt[N*2],v[N*2],c[N*2];int size[N],big[N],d[N],nph[N];int cnt[N*2],soncnt[N*2],nphcnt[N*2];struct data{int sum,x;bool flag;}son[N];bool vis[N];LL ans;void add(int x,int y,int z){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;}void getroot(int x,int fa){ size[x]=1;big[x]=0; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { getroot(v[i],x); size[x]+=size[v[i]]; big[x]=max(big[x],size[v[i]]); } big[x]=max(big[x],sum-size[x]); if (big[x]<big[root]) root=x;}void getdeep(int x,int fa){ for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { d[v[i]]=d[x]+c[i]; son[++cs].sum=d[v[i]]; son[cs].x=v[i]; if (cnt[d[v[i]]+base]) { son[cs].flag=1; nph[++cn]=d[v[i]]; } else son[cs].flag=0; ++cnt[d[v[i]]+base]; getdeep(v[i],x); --cnt[d[v[i]]+base]; }}LL calc(int x,int now){ d[x]=now; cs=cn=0; if (now) { son[++cs].sum=now,son[cs].flag=0; son[cs].x=x; ++cnt[now+base]; } getdeep(x,0); if (now) --cnt[now+base]; for (int i=1;i<=cs;++i) ++soncnt[son[i].sum+base]; for (int i=1;i<=cn;++i) ++nphcnt[nph[i]+base]; LL t=0LL,count0=0LL,alone=0LL; for (int i=1;i<=cs;++i) { if (son[i].sum==0) { ++count0; if (son[i].flag) ++alone; continue; } if (son[i].flag==1) t+=(LL)soncnt[-son[i].sum+base]; else t+=(LL)nphcnt[-son[i].sum+base]; } for (int i=1;i<=cs;++i) --soncnt[son[i].sum+base]; for (int i=1;i<=cn;++i) --nphcnt[nph[i]+base]; LL re; if (!now) re=t/2LL+count0*(count0-1LL)/2LL+alone; else re=t/2LL+count0*(count0-1LL)/2LL; return re;}void dfs(int x){ ans+=calc(x,0); vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { ans-=calc(v[i],c[i]); sum=size[v[i]];root=0; getroot(v[i],0); dfs(root); }}int main(){ scanf("%d",&n); for (int i=1;i<n;++i) { scanf("%d%d%d",&x,&y,&z); if (!z) z=-1; add(x,y,z),add(y,x,z); } big[0]=N; sum=n;root=0; getroot(1,0); dfs(root); PRintf("%lld/n",ans);}

上一篇：Lucene初探之数据格式详情（-）

下一篇：网页Web上调用本地应用程序（.exe）