#C241011A. 点分治

标签（Label）

• 点分治

• 模板

网址（Website）

题目详情 - 【NOI模板】树分治 - 点分治 - 聪聪可可「国家集训队」 - Super

P2634 [国家集训队] 聪聪可可 - 洛谷

练习题： #C241010B. 旅游

题解（Solution）

代码实现的时候有几个注意的点：

• 子连通块大小不要直接用 $siz[to]$ ，在访问父亲的连通块的时候会出问题。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 201234;
bool ST;

vector<P> ft[N];
int n,zi,mu,root,maxx;

int sub[N],siz[N];
bitset<N> vst;
inline void dfs_root(int x,int fa,int sum){
	siz[x] = 1;
	int s=0;
	for(auto p:ft[x]){
		int y = p.x;
		if(y==fa || vst[y]) continue;
		dfs_root(y,x,sum);
		siz[x] += siz[y];
		s = max(s, siz[y]);
	}s = max(s, sum-siz[x]);
	if(s < maxx) maxx = s,root=x;
}

int dis[N],dep[N],tot;
inline void dfs_dis(int x,int fa){
	dep[++tot] = dis[x]%3;
	for(auto p:ft[x]){
		int y = p.x, v = p.y;
		if(y==fa || vst[y]) continue;
		dis[y] = dis[x]+v;
		dfs_dis(y,x);
	}
}

inline int cal(int l,int r){
	array<int,3> way = {0,0,0};
	For(i,l,r) way[dep[i]]++,assert(dep[i]<3);
	return way[0]*way[0] + way[1]*way[2]*2;
}

inline int calc(int x){
	int res = 0;tot = 0;
	dep[++tot] = dis[x] = 0;
	for(auto p:ft[x]){
		int y = p.x, v = p.y;
		if(vst[y]) continue;
		int l = tot+1;
		dis[y] = dis[x]+v;
		dfs_dis(y,x);
		int r = tot;
		res -= cal(l,r);
	}
	res += cal(1,tot);
	return res;
}

inline void devide(int x){
	vst[x] = true;
	zi += calc(x);
	for(auto p:ft[x]){
		int y = p.x;
		if(vst[y]) continue;
		sub[root = 0] = N;
		maxx=siz[y];
		dfs_root(y,x,siz[y]);
		devide(root);
	}
}
int g(int a,int b){
	if(!b) return a;
	return g(b,a%b);
}
void solve(){
	n = rd();For(i,1,n-1){
		int x = rd(), y = rd(), v = rd();
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}mu = n*n;
	
	sub[root = 0] = N;
	maxx=n;
	dfs_root(1,0,n);
	devide(root);
	
	int gg = g(zi,mu);
	printf("%d/%d\n",zi/gg,mu/gg);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}