「BZOJ 2152」聪聪可可

题目链接

戳这

\(Solution\)

这道题看起来就像点分治对吧.没错就是点分治.

什么是点分治

如果你不会点分治,可以去看看这儿

现在看到这里,首先确保你已经会了点分治,如果不会你还往下看,听不懂概不负责虽然会但没看懂也不负责(逃)

点分治题目大部分都是模板对吧.只是calc(solve)的区别.首先看看暴力的calc.暴力枚举所有边,在判断是否为3的倍数.

但是这显然不行对吧,在仔细思考一下.发现%3的数的可能性只有三种情况

%3=0
%3=1
%3=2

所以想要为三的倍数的话有两种可能性,0和0的组和,1和2的组合所以答案就是dis[1]*dis[2]*2+dis[0]*dis[0]最后的答案就是这个出以总方案数.记得约分.

\(Code\)

// luogu-judger-enable-o2

#include<bits/stdc++.h>

using namespace std;

const int N=40001;

int read() {

	int x=0,f=1;

	char c=getchar();

	while(c<'0'||c>'9')c=='-'?f=-1,c=getchar():c=getchar();

	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();

	return x*f;

}

int n,k;

int dep[N];

int f[N];

int vis[N];

int siz[N];

int root;

struct node {

	int next,to,v;

} a[N<<1];

int head[N],cnt,sum;

void add(int x,int y,int c) {

	a[++cnt].to=y;

	a[cnt].next=head[x];

	a[cnt].v=c;

	head[x]=cnt;

}

void findroot(int k,int fa) {

	f[k]=0,siz[k]=1;

	for(int i=head[k]; i; i=a[i].next) {

		int v=a[i].to;

		if(vis[v]||v==fa)

			continue;

		findroot(v,k);

		siz[k]+=siz[v];

		f[k]=max(f[k],siz[v]);

	}

	f[k]=max(f[k],sum-siz[k]);

	if(f[k]<f[root])

		root=k;

}

int tot;

void finddep(int k,int fa,int l) {

	dep[l]++;

	for(int i=head[k]; i; i=a[i].next) {

		int v=a[i].to;

		if(v==fa||vis[v])

			continue;

		finddep(v,k,(l+a[i].v)%3);

	}

}

int calc(int k,int L) {

	tot=0;

	dep[0]=dep[1]=dep[2]=0;

	finddep(k,0,L%3);

	return dep[0]*dep[0]+2*dep[1]*dep[2];

}

int js;

void devide(int k) {

	vis[k]=1;

	js+=calc(k,0);

	for(int i=head[k]; i; i=a[i].next) {

		int v=a[i].to;

		if(vis[v])

			continue;

		js-=calc(v,a[i].v);

		root=0,sum=siz[v];

		findroot(v,0);

		devide(root);

	}

}

int main() {

	int n=read(),x,y,z;

	for (int i=1; i<n; i++)

		x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);

	sum=f[0]=n;

	findroot(1,0);

	devide(root);

	int l=__gcd(js,n*n);

	printf("%d/%d\n",js/l,n*n/l);

	return 0;

}

巴特西

「BZOJ 2152」聪聪可可

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章