bzoj2152(点分治)

Posted on   |   In

题解

点分治模板题

不同的是 我们不需要sort 也不需要去重

对于每个子树重心做一个树$dp$即可 $dp[x][y]$表示x的子树中到x距离模3后y的个数

然后对于每个子树重心 合并维护答案即可

$复杂度O(nlogn)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
const int inf=1e9;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int n;
int base,key,pos,sz[MAXN],maxx[MAXN],rt;
bool vis[MAXN];
void get_root(int x,int pre){
    sz[x]=1;maxx[x]=0;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	get_root(j->t,x);
	sz[x]+=sz[j->t];maxx[x]=max(maxx[x],sz[j->t]);
    }
    maxx[x]=max(maxx[x],base-sz[x]);
    if(key>maxx[x])key=maxx[x],rt=x;
}

int t[MAXN][4];
ll dis[MAXN];
void dfs(int x,int pre){
    t[x][0]=t[x][1]=t[x][2]=0;
    t[x][dis[x]%3]++;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	dis[j->t]=dis[x]+j->v;
	dfs(j->t,x);
	t[x][0]+=t[j->t][0];t[x][1]+=t[j->t][1];t[x][2]+=t[j->t][2];
    }
}

ll ans;

void solve(int x,int pre){
    vis[x]=1;dis[x]=0;
    dfs(x,0);
    t[x][0]=t[x][1]=t[x][2]=0;t[x][0]++;
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	ans+=1ll*t[x][0]*t[j->t][0];
	ans+=1ll*t[x][1]*t[j->t][2];
	ans+=1ll*t[x][2]*t[j->t][1];
	t[x][0]+=t[j->t][0];t[x][1]+=t[j->t][1];t[x][2]+=t[j->t][2];
    }
    link(x){
	if(vis[j->t]||j->t==pre)continue;
	key=inf;base=sz[j->t];get_root(j->t,x);
	solve(rt,0);
    }
}



int main(){
    n=read();
    int x,y,z;
    inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    ans=0;
    base=n;key=inf;get_root(1,0);
    solve(rt,0);
    ll t1=2*ans+n;ll t2=1ll*n*n;
    ll t=__gcd(t1,t2);t1/=t;t2/=t;
    printf("%lld/%lld\n",t1,t2);
    return 0;
}

题目描述

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画$n$个“点”，并用$n-1$条“边”把这$n$个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是$3$的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第1行包含1个正整数$n$。后面$n-1$行，每行$3$个整数$x、y、w$，表示$x$号点和$y$号点之间有一条边，上面的数是$w$。

Output

以即约分数形式输出这个概率（即$“a/b”$的形式，其中$a$和$b$必须互质。如果概率为$1$，输出$“1/1”$）。