A simple Blog for wyx I've been down the bottle hoping.
POJ 点分治 1741
发表于: | 分类: Oi | 评论:0 | 阅读:39

题意:给定一棵树,求满足 $dis(u,k) \le k$ 的点对的个数,$n\le 10000$ , 没有满足条件的输出-1、

题解:点分治的例题,首先我们可以发现,一条链一定存在某个点可以作为一棵子树的根,或者说其实任意选择链上一个点做根,就能使得这玩意变成一个过根的东西
先考虑如果确定了根是谁怎么统计
我们可以先求一下每个点到根节点的距离然后把他们排序放在一起双指针扫一下 具体大概是这样的
我们最开始的时候把左指针指向最小的元素,右指针指向最大的元素,然后我们每次看左右指针所对的值加和是否小于等于 $k$ ,如果是,说明对于左指针而言,左右指针所夹的部分加和都是 $\le k$ 的,因为我们排序了,这个时候我们把答案加上左指针的区间长度,然后左指针右移,否则右指针左移知道满足刚才的条件,或者左右指针重合
但是我们会发现这样做有一个小问题,可能存在一棵子树内的两个点,他们俩的简单路径其实并不过根,但是却被统计到了答案中,但是对于这种情况也好办,我们重新遍历一下这棵树的部分,然后把这些深度放在一起,还按照刚才的统计方法统计,然后用刚才的答案减去这个部分就都是合法的了,因为刚才的不合法部分就是这些数字组成的

现在我们来考虑分治
我们现在能统计出过一个点的链了,但是我们还需要处理一下不经过这个点的链,我们可以挖去这个点,然后统计一下剩余部分的答案,显然挖去这个点绝对是不影响答案的,因为与这个点相关的答案我们都已经统计完了,然后我们继续扣掉其他的点进行计算就行了
但是这个复杂度其实太爆炸了,极限情况其实是 $\frac{n^2}{2}*log(n)$ 的。

但是我们观察到,答案其实和选根做点的顺序并没有什么关系(刚才已经说过了)
于是我们可以想一些办法吧树的规模变小处理
我们可以每次选择一棵树的重心,重心的定义是一颗树去掉一个点使得剩余部分都不大于原树大小的一半

这样的话,每次选走一个点做根,剩下的大小必然减小一半,也就是由原来的 $n$ 层处理变成了 $log(n)$ 层处理
每一层每个点最多被遍历一次再加上一次排序
这个复杂度就是完美的 $O(nlog^2(n))$啦

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 10000+5;
const int M = N << 1;
using namespace std;

int head[N];
bool vis[N];
int sum,k,n;

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

int cnt;

inline void add(int x,int y,int z)
{
    edge[++cnt] = graph(head[x],y,z); head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z); head[y] = cnt;
}

int size[N],root;
int F[N];

void DFS1(int x,int fa)
{
    size[x] = 1; F[x] = 0;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to])
        {
            DFS1(edge[i].to,x);
            size[x] += size[edge[i].to];
            F[x] = max(F[x],size[edge[i].to]);
        }
    F[x] = max(F[x],sum - size[x]);
    if(F[x] < F[root]) root = x;
}

int stack[N],top;
int dis[N];

void DFS2(int x,int fa)
{
    stack[++top] = dis[x];
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to != fa && !vis[edge[i].to])
        {
            dis[edge[i].to] = dis[x] + edge[i].val;
            DFS2(edge[i].to,x);
        }
}

int work(int x,int now)
{
    dis[x] = now;
    top = 0;
    DFS2(x,x);
    sort(stack+1,stack+top+1);
    int l = 1,r = top,ans = 0;
    while(l < r)
    {
        while(stack[r] + stack[l] > k && l < r) r --;
        ans += r - l; l ++; 
    }
    return ans;
}

int ans;

void solve(int x)
{
    ans += work(x,0); vis[x] = 1;
    for(int i=head[x];i;i=edge[i].next)
        if(!vis[edge[i].to])
        {
            ans -= work(edge[i].to,edge[i].val);
            root = 0; 
            sum = size[edge[i].to];
            DFS1(edge[i].to,root);
            solve(root);
        }
}


void init()
{
    memset(F,0,sizeof F);
    memset(dis,0,sizeof dis);
    memset(head,0,sizeof head);
    memset(vis,false,sizeof vis);
    cnt = root = sum = ans = 0;
}

int main()
{
    while(1)
    {
        init();
        cin >> n >> k;
        if(!n && !k) return 0;
        int x,y,z;
        for(int i=1;i<n;++i)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        sum = n;
        F[0] = 0x3f3f3f3f;
        DFS1(1,0);
        solve(root);
        printf("%d\n",ans);
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP