首页 > 代码库 > BZOJ3697: 采药人的路径
BZOJ3697: 采药人的路径
传送门
不是那么裸的点分治。
$f[i][0/1]$表示当前节点的一个子树中总权值和为$i$，且是否存在一个前缀使得其前缀和为$i$
$g[i][0/1]$表示当前节点的已遍历过的子树，其余一样。
对于每个节点
$ans_{node}=g[0][0]∗f[0][0]+ \sum (g[−i][0]∗f[i][1]+g[−i][1]∗f[i][0]+g[−i][1]∗f[i][1])$
另外，Race那道题选根的方案在这里好像不是很适用，容易出问题，还是换黄学长的比较好。
1 //BZOJ 3697 2 //by Cydiater 3 //2016.9.26 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <queue> 10 #include <map> 11 #include <ctime> 12 #include <cmath> 13 #include <iomanip> 14 #include <cstdlib> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n) for(int i=j;i<=n;i++) 18 #define down(i,j,n) for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22 char ch=getchar();int x=0,f=1; 23 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25 return x*f; 26 } 27 int N,LINK[MAXN],len=0,sum,root,siz[MAXN],dis[MAXN],pre[MAXN],deep[MAXN]; 28 int maxdeep,max_siz[MAXN]; 29 ll ans=0,f[MAXN][2],g[MAXN][2]; 30 bool vis[MAXN]; 31 struct edge{ 32 int y,next,v; 33 }e[MAXN]; 34 namespace solution{ 35 inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;} 36 void init(){ 37 N=read(); 38 up(i,2,N){ 39 ll x=read(),y=read(),v=read()==0?-1:1; 40 insert(x,y,v); 41 insert(y,x,v); 42 } 43 } 44 void make_root(int node,int fa){ 45 max_siz[node]=0;siz[node]=1; 46 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){ 47 make_root(e[i].y,node); 48 siz[node]+=siz[e[i].y]; 49 max_siz[node]=max(max_siz[node],siz[e[i].y]); 50 } 51 max_siz[node]=max(max_siz[node],sum-max_siz[node]); 52 if(max_siz[node]<max_siz[root])root=node; 53 } 54 void dfs(int node,int father){ 55 if(pre[dis[node]]) f[dis[node]][1]++; 56 else f[dis[node]][0]++; 57 pre[dis[node]]++; 58 maxdeep=max(deep[node],maxdeep); 59 for(int i=LINK[node];i;i=e[i].next) 60 if(e[i].y!=father&&!vis[e[i].y]){ 61 deep[e[i].y]=deep[node]+1; 62 dis[e[i].y]=dis[node]+e[i].v; 63 dfs(e[i].y,node); 64 } 65 pre[dis[node]]--; 66 } 67 void work(int node){ 68 vis[node]=1;g[N][0]=1;int mx=0; 69 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){ 70 dis[e[i].y]=e[i].v+N;deep[e[i].y]=1;maxdeep=1; 71 dfs(e[i].y,0);mx=max(mx,maxdeep); 72 ans+=1LL*(g[N][0]-1)*f[N][0]; 73 up(k,-maxdeep,maxdeep) 74 ans+=1LL*g[N-k][0]*f[N+k][1]+1LL*g[N-k][1]*f[N+k][0]+1LL*g[N-k][1]*f[N+k][1]; 75 up(j,N-maxdeep,N+maxdeep){ 76 g[j][0]+=f[j][0]; 77 g[j][1]+=f[j][1]; 78 f[j][0]=f[j][1]=0; 79 } 80 } 81 up(j,N-mx,N+mx)g[j][0]=g[j][1]=0; 82 for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){ 83 root=0;sum=siz[e[i].y]; 84 make_root(e[i].y,0); 85 work(root); 86 } 87 } 88 void slove(){ 89 sum=N;root=0;max_siz[root]=N; 90 make_root(1,0); 91 work(root); 92 } 93 void output(){ 94 cout<<ans<<endl; 95 } 96 } 97 int main(){ 98 //freopen("input.in","r",stdin); 99 using namespace solution;100 init();101 slove();102 output();103 return 0;104 }
BZOJ3697: 采药人的路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。