icontofig | 发布于 2020-02-03 23:19:32 | 阅读量 372 | 点分治 树状数组
发布于 2020-02-03 23:19:32 | 点分治 树状数组

题解

树上点对距离问题,非常经典的点分治问题。

点分治的基本思路:

对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。

重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。

重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。

此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。

可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理一下。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct edge{
    int to,next,val;
}e[maxn<<1];
int siz[maxn],mx[maxn],vis[maxn],dis[maxn];
int c[maxn*100],tmp[maxn];
int n,rt;
int h[maxn];
int lowbit(int x){
    return x & -x;
}
void update(int now,int d){
    while(now <= n * 100 - 2){
        c[now] += d;
        now += lowbit(now);
    }
    return;
}
int query(int now){
    int ret = 0;
    while(now > 0){
        ret += c[now];
        now -= lowbit(now);
    }
    return ret;
}
int cnt = 0,num = 0,sum = 0;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].val = d;e[cnt].next = h[u];h[u] = cnt++;
    return;
}
void get_root(int now,int fa){
    siz[now] = 1;mx[now] = 0;
    for(int i = h[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(vis[v] || v == fa)continue;
        get_root(v,now);
        siz[now] += siz[v];
        if(siz[v] > mx[now])
            mx[now] = siz[v];
    }
    mx[now] = max(mx[now],sum - siz[now]);
    if(mx[now] < mx[rt])
        rt = now;
    return;
}
void get_dis(int now,int fa){
    tmp[++num] = dis[now];
    for(int i = h[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(v == fa || vis[v])continue;
        dis[v] = dis[now] + e[i].val;
        get_dis(v,now);
    }
    return;
}
int ans = 0,k;
void solve(int now){
    queue<int>q;
    q.push(0);
    update(1,1);
    for(int i = h[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(vis[v])continue;
        num = 0;
        dis[v] = e[i].val;
        get_dis(v,now);
        for(int j = 1;j <= num;++j){
            if(tmp[j] > k)continue;
            ans += query(k - tmp[j] + 1);
        }
        for(int j = 1;j <= num;++j){
            q.push(tmp[j]);
            update(tmp[j]+1,1);
        }
    }
    while(!q.empty()){
        update(q.front()+1,-1);
        q.pop();
    }
    return;
}
void divid(int now){
    vis[now] = 1;
    solve(now);
    for(int i = h[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(vis[v])continue;
        mx[rt = 0] = sum = siz[v];
        get_root(v,0);
        get_root(rt,0);
        divid(rt);
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n;
    int a,b,dd;
    memset(h,-1,sizeof(h));
    for(int i = 1;i < n;++i){
        cin >> a >> b >> dd;
        add(a,b,dd);
        add(b,a,dd);
    }
    cin >> k;
    mx[rt = 0] = sum = n;
    get_root(1,0);
    get_root(rt,0);
    divid(rt);
    cout << ans << endl;
    return 0;
}



内容更新于: 2020-02-03 23:19:36
链接地址: http://blog.leanote.com/post/icontofig/82167aca3965

上一篇: 51Nod 1601 完全图的最小生成树计数 kruskal + trie异或运算贪心

下一篇: 一个看起来飞快的AC自动机模板

372 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航