欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ 2152 聪聪可可 | 树分治

程序员文章站 2022-05-08 18:26:26
...

题目:

给一棵点带权树,求树上路径是三的倍数的路径与总路径个数之比,输出最简分数


题解:

树分治

建一个cnt数组储存长度%3的路径有多少

计算的时候return cnt[0]*cnt[0]+cnt[1]*cnt[2]*2

其他的同树分治板子了

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 20005
typedef long long ll;
using namespace std;
ll n,K,fa[N],sze[N],son[N],dis[N],head[N],ecnt,ans,tot;
bool vis[N];
struct edge {ll nxt,v,w;}e[2*N];
ll gcd(ll x,ll y) { return y==0?x:gcd(y,x%y);}
void add(ll u,ll v,ll w)
{
    e[++ecnt].v=v,e[ecnt].w=w,e[ecnt].nxt=head[u],head[u]=ecnt;
    e[++ecnt].v=u,e[ecnt].w=w,e[ecnt].nxt=head[v],head[v]=ecnt;
}
int calcG(int sv)
{
    static int qn,que[N];
    int u,v,mx=n,G; 
    que[qn=1]=sv,fa[sv]=0;
    for (int ql=1;ql<=qn;ql++)
    {
	sze[u=que[ql]]=1,son[u]=0;
	for (int i=head[u];i;i=e[i].nxt)
	{
	    if (vis[v=e[i].v] || v==fa[u]) continue;
	    fa[v]=u,que[++qn]=v;
	}
    }
    for (int ql=qn;ql>=1;ql--)
    {
	u=que[ql],v=fa[u];
	if (qn-sze[u]>son[u]) son[u]=qn-sze[u];
	if (son[u]<mx) G=u,mx=son[u];
	if (!v) break;
	sze[v]+=sze[u];
	if (sze[u]>son[v]) son[v]=sze[u];
    }
    return G;
}
inline ll calc(int sv,ll L)
{
    static int qn,que[N];
    int cnt[4],u,v;
    memset(cnt,0,sizeof(cnt));
    que[qn=1]=sv,dis[sv]=L,fa[sv]=0;
    for (int ql=1;ql<=qn;ql++)
    {
	cnt[dis[u=que[ql]]%3]++;
	for (int i=head[u];i;i=e[i].nxt)
	    if (vis[v=e[i].v] || v==fa[u]) continue ;
	    else  fa[v]=u,dis[v]=dis[u]+e[i].w,que[++qn]=v;
    }
    return cnt[0]*cnt[0]+cnt[1]*cnt[2]*2;
}
void solve(int u)
{
    int G=calcG(u);
    vis[G]=1;
    ans+=calc(G,0);
    for (int i=head[G];i;i=e[i].nxt)
	if (!vis[e[i].v]) ans-=calc(e[i].v,e[i].w);
    for (int i=head[G];i;i=e[i].nxt)
	if (!vis[e[i].v]) solve(e[i].v);
}
int main()
{
    scanf("%lld",&n);
    for (ll i=1,u,v,w;i<n;i++)
    {
	scanf("%lld%lld%lld",&u,&v,&w);
	add(u,v,w%3);
    }
    solve(1);
    ll G=gcd(ans,tot=n*n);
    printf("%lld/%lld\n",ans/G,tot/G);
    return 0;
}