首页 > 代码库 > AC日记——【模板】点分治(聪聪可可) 洛谷 P2634
AC日记——【模板】点分治(聪聪可可) 洛谷 P2634
【模板】点分治(聪聪可可)
思路:
点分治;
(感谢灯神)
代码:
#include <bits/stdc++.h>using namespace std;#define maxn 20005#define INF 0x7fffffffint n,m,sum,num,cnt,ans,L,root,t;int head[maxn],vis[maxn],d[maxn];int size[maxn],lar[maxn],flag[4];int E[maxn<<1],V[maxn<<1],W[maxn<<1];inline void in(int &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘)Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}inline void edge_add(int u,int v,int w){ E[++cnt]=head[u],V[cnt]=v,W[cnt]=w,head[u]=cnt; E[++cnt]=head[v],V[cnt]=u,W[cnt]=w,head[v]=cnt;}inline int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}void GetRoot(int now,int fa){ size[now]=1,lar[now]=0; for(int i=head[now];i;i=E[i]) { if(V[i]==fa||vis[V[i]]) continue; GetRoot(V[i],now); size[now]+=size[V[i]]; lar[now]=max(lar[now],size[V[i]]); } lar[now]=max(lar[now],sum-size[now]); if(lar[now]<lar[root]) root=now;}void GetDeep(int now,int fa){ flag[d[now]]++; for(int i=head[now];i;i=E[i]) { if(vis[V[i]]||V[i]==fa)continue; d[V[i]]=(d[now]+W[i])%3; GetDeep(V[i],now); }}int cal(int now,int dis){ d[now]=dis,flag[0]=flag[1]=flag[2]=0; GetDeep(now,0); return flag[1]*flag[2]*2+flag[0]*flag[0];}void work(int now){ ans+=cal(now,0),vis[now]=1; for(int i=head[now];i;i=E[i]) { if(vis[V[i]]) continue; ans-=cal(V[i],W[i]); root=0,sum=size[V[i]]; GetRoot(V[i],0),work(root); }}int main(){ in(n);int u,v,w; for(int i=1;i<n;i++) { in(u),in(v),in(w); edge_add(u,v,w%3); } sum=n,lar[0]=n+1; GetRoot(1,0),work(root); t=gcd(ans,n*n); printf("%d/%d\n",ans/t,n*n/t); return 0;}
AC日记——【模板】点分治(聪聪可可) 洛谷 P2634
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。