【BZOJ 2152】聪聪可可 点分治

对于一棵树,fdrt找到重心,然后分治每个子树。

在一棵以重心为根的树上,符合条件的链是:

  1.过重心(根)

  2.不过重心

对于1我们只需dfs出距离重心(根)的距离然后统计再减去有重叠的边

对于2我们只需递归处理子树,这样2就分为过子树的根(重心)的链和不过子树根(重心)的链······

这就是点分治啦,貌似边分治更优,但是为了减少代码量,效率什么的我统统都不要(╬▔皿▔)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N=20003;
inline const int max( const int &a, const int &b) {return a>b?a:b;}
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
struct node {
int nxt, to, w;
} E[N<<1];
int point[N], size[N], ma[N], n, cnt=0, rt=0, ans=0, table[N], tn, di[N];
bool vis[N];
inline void insect( int x, int y, int z) {
cnt++;
E[cnt].nxt = point[x];
E[cnt].to = y;
E[cnt].w = z;
point[x] = cnt;
}
inline void fdrt( int x, int fa, int s) {
size[x] = 1;
ma[x] = 0;
for( int tmp = point[x]; tmp; tmp = E[tmp].nxt)
if ( !vis[E[tmp].to] && E[tmp].to != fa) {
fdrt( E[tmp].to, x, s);
size[x] += size[E[tmp].to];
ma[x] = max( ma[x], size[E[tmp].to]);
}
if ( s - ma[x] > ma[x])
ma[x] = s - ma[x];
if ( ma[x] < ma[rt])
rt = x;
}
inline void mktb( int x, int fa) {
table[ ++tn] = di[x];
for( int tmp = point[x]; tmp; tmp = E[tmp].nxt)
if ( !vis[E[tmp].to] && E[tmp].to != fa) {
di[E[tmp].to] = di[x] + E[tmp].w;
mktb( E[tmp].to, x);
}
}
inline int work( int x, int beg) {
int cn0 = 0, cn1 = 0, cn2 = 0;
tn = 0;
di[x] = beg;
mktb( x, -1);
for( int i = 1; i <= tn; ++i) {
switch ( table[i] % 3) {
case 0:
++cn0;
break;
case 1:
++cn1;
break;
case 2:
++cn2;
break;
}
}
return cn0 * cn0 + ( ( cn1 * cn2) << 1);
}
inline void dfs( int x, int s) {
vis[x] = 1;
ans += work( x, 0);
for( int tmp = point[x], ss; tmp; tmp = E[tmp].nxt)
if ( !vis[E[tmp].to]) {
ans -= work( E[tmp].to, E[tmp].w);
if ( size[E[tmp].to] > size[x])
ss = s - size[x];
else
ss = size[E[tmp].to];
rt = 0;
fdrt( E[tmp].to, x, ss);
dfs( rt, ss);
}
}
inline int gcd( int x, int y) {
int r = x % y;
while ( r) {
x = y;
y = r;
r = x % y;
}
return y;
}
int main() {
read( n);
int u, v, e;
for( int i = 1; i < n; ++i) {
read( u);
read( v);
read( e);
e %= 3;
insect( u, v, e);
insect( v, u, e);
}
ma[0] = n+3;
memset( vis, 0, sizeof(vis));
fdrt( (n+1)>>1, -1, n);
dfs( rt, n);
int m = n * n, tong = gcd( ans, m);
printf( "%d/%d\n", ans / tong, m / tong);
return 0;
}

点分治完成啦,找重心估计s时偷了点懒效率立刻就低了∑(っ °Д °;)っ还是改回来了

还有我的码风这次有点奇怪⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄.是不是不再像以前那么挤了ヾ (o ° ω ° O ) ノ゙

上一篇:【云计算】Docker集中化web界面管理平台shipyard


下一篇:poj1155 TELE (树上的背包)