简单点分治

Tree

题目描述

给定一棵 n 个节点的树,每条边有边权,求出树上两点距离小于等于 k 的点对数量。

输入格式

第一行输入一个整数 n,表示节点个数。

第二行到第 n 行每行输入三个整数 u,v,w ,表示 uv 有一条边,边权是 w

n+1 行一个整数 k

输出格式

一行一个整数,表示答案。

样例 #1

样例输入 #1

7
1 6 13 
6 3 9 
3 5 7 
4 1 3 
2 4 20 
4 7 2 
10

样例输出 #1

5

提示

数据规模与约定

对于全部的测试点,保证:

  • $1\leq n\leq 4\times 10^4$。
  • $1\leq u,v\leq n$。
  • $0\leq w\leq 10^3$。
  • $0\leq k\leq 2\times 10^4$。

由于这里查询的是树上距离为 的点对数量,所以我们用线段树来支持维护和查询

注意

– 点分治dfs,无cint
– 树状数组,点分治,下标+1

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
using namespace std;
using cint = int;
constexpr int maxn = 40010, inf = 2e9;
struct {
    int nxt, v, w;
}edge[maxn << 1];
int siz[maxn], rt, maxq, sum, maxsiz, minsiz, dis[maxn], discnt, n, m, u, v, w, k, cnt, head[maxn], q[maxn];
bool vis[maxn];
queue<int> tip;

struct treeary {
    using mint = int;
    mint t[maxn];
    inline void add(cint x, const mint& v) {
        for (int i = x + 1; i <= k + 1; i += lowbit(i)) t[i] += v;
    }
    inline mint get(cint x) {
        mint ans = 0;
        for (int i = x + 1; i; i -= lowbit(i)) ans += t[i];
        return ans;
    }
}t;


inline void addedge(cint u, cint v, cint w) {
    edge[++cnt] = { .nxt = head[u],.v = v,.w = w };
    head[u] = cnt;
}
void getsiz(cint x, cint fa) {
    siz[x] = 1;
    int maxsiz = 0;
    for (auto i = head[x]; i; i = edge[i].nxt) {
        const auto v = edge[i].v;
        if (v == fa || vis[v]) continue;
        getsiz(v, x);
        siz[x] += siz[v];
        maxsiz = max(siz[v], maxsiz);
    }
    maxsiz = max(maxsiz, sum - siz[x]);
    if (maxsiz < minsiz) rt = x, minsiz = maxsiz;
}
void getdis(cint x, cint fa, cint disx) {
    if (disx <= k) dis[++discnt] = disx;
    for (auto i = head[x]; i; i = edge[i].nxt) {
        const auto v = edge[i].v;
        if (v == fa || vis[v]) continue;
        getdis(v, x, disx + edge[i].w);
    }
}
int ansqwq;
inline void check(cint dis) {
    ansqwq += t.get(k - dis);
}

void dfs(cint x, cint fa) {
    vis[x] = 1;
    tip.push(0); t.add(0, 1);
    for (int i = head[x]; i; i = edge[i].nxt) {
        const int v = edge[i].v;
        if (v == fa || vis[v]) continue;
        discnt = 0;
        getdis(v, x, edge[i].w);
        for (int j = 1; j <= discnt; ++j) check(dis[j]);
        for (int j = 1; j <= discnt; ++j) tip.push(dis[j]), t.add(dis[j], 1);
    }
    while (!tip.empty())
        t.add(tip.front(), -1), tip.pop();
    for (int i = head[x]; i; i = edge[i].nxt) {
        const int v = edge[i].v;
        if (v == fa || vis[v]) continue;
        sum = siz[v];
        rt = 0;
        minsiz = inf;
        getsiz(v, x);
        getsiz(rt, -1);
        dfs(rt, x);
    }
}
signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        addedge(u, v, w), addedge(v, u, w);
    }
    cin >> k;
    rt = 0;
    minsiz = inf;
    sum = n;
    getsiz(1, -1);
    getsiz(rt, -1);
    dfs(rt, -1);
    cout << ansqwq;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇