首页 > 其他分享 >点分治

点分治

时间：2024-08-20 16:48:08浏览次数：5  
标签：rt 10 int 分治 read include getchar

点分治

点分治是一个求树上路径问题的算法，算法流程通常是：找到子树中的重心，计算重心的子树的每一个点与重心的路径的数据，接着统计整体答案。

Close Vertices

思路

很明显，这是一道点分治题目，但有两个限制条件，考虑将两个条件排序起来，双指针找第一个条件，树状数组维护第二个条件，但是同一个子树内不能重复统计，所以将答案减去每个子树内的答案。

代码

#include<iostream>
#include<algorithm>
#define int long long

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 4e5 + 10;
int n, k, d, maxn, rt, ans;
int t[N];
int lowbit(int x){return x & (-x);}
void modify(int x, int y){
    for (int i = max(x, 1ll); i <= 1e5 + 1; i += lowbit(i)) t[i] += y;
}
int query(int x){
    int res = 0;
    for (int i = max(x, 1ll); i; i -= lowbit(i)) res += t[i];
    return res;
}
struct edge{
    int v, w, nxt;
}e[N << 1];
int head[N], cnt;
void add(int u, int v, int w){
    e[++cnt] = (edge){v, w, head[u]};
    head[u] = cnt;
}
struct node{
    int dis, l;
    bool operator < (const node &b) const{
        if (dis != b.dis) return dis < b.dis;
        return l < b.l;
    }
}stk1[N], stk2[N];
int mx[N], sz[N], top1, top2, dis[N], l[N];
bool vis[N];
void find(int u, int fa){
    sz[u] = 1, mx[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        find(v, u);
        sz[u] += sz[v];
        mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], maxn - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}
void dfs(int u, int fa){
    stk2[++top2] = (node){dis[u], l[u]};
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        dis[v] = dis[u] + e[i].w;
        l[v] = l[u] + 1;
        dfs(v, u);
    }
}
void calc(int u){
    top1 = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        top2 = 0, dis[v] = e[i].w, l[v] = 1;
        dfs(v, u);
        sort(stk2 + 1, stk2 + top2 + 1);
        for (int j = 1; j <= top2; j++) stk1[++top1] = stk2[j], modify(stk2[j].l + 1, 1);
        int l = 1, r = top2;
        while (l <= top2){
            modify(stk2[l].l + 1, -1);
            while (l < r && stk2[l].dis + stk2[r].dis > d) modify(stk2[r--].l + 1, -1);
            if (l >= r) break;
            ans -= query(k - stk2[l].l + 1);
            l++;
        }
    }
    stk1[++top1] = (node){0, 0};
    sort(stk1 + 1, stk1 + top1 + 1);
    for (int i = 1; i <= top1; i++) modify(stk1[i].l + 1, 1);
    int l = 1, r = top1;
    while (l <= top1){
        modify(stk1[l].l + 1, -1);
        while (l < r && stk1[l].dis + stk1[r].dis > d) modify(stk1[r--].l + 1, -1);
        if (l >= r) break;
        ans += query(k - stk1[l].l + 1);
        l++;
    }
}
void solve(int u){
    vis[u] = 1;
    calc(u);
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        maxn = sz[v];
        rt = 0;
        find(v, 0);
        solve(rt);
    }
}

signed main(){
    n = read(), k = read(), d = read();
    for (int i = 1; i < n; i++){
        int v = read(), w = read();
        add(i + 1, v, w), add(v, i + 1, w);
    }
    maxn = mx[rt] = n;
    find(1, 0);
    solve(rt);
    cout << ans;
    return 0;
}

Luogu 的 CF Remotejudge 没修好，气死我也。

P5351 Ruri Loves Maschera

思路

首先，路径的最大值很好计算出来，考虑如何统计答案，对于一条权值为 \(k\) 的链，用树状数组查询比 \(k\) 小的个数，这些边的权值都为 \(k\)，因为每个链都会被大于其权值的链统计，所以只需统计小于其权值的然后匹配即可，注意要容斥。

代码

#include<iostream>
#include<algorithm>

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 1e5 + 10;
int n, L, R, rt;
long long ans;
int t[N];
int lowbit(int x){return x & -x;}
void modify(int x, int y){
    for (int i = x; i <= n + 1; i += lowbit(i)) t[i] += y;
}
int query(int x){
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += t[i];
    return res;
}
struct edge{
    int v, w, nxt;
}e[N << 1];
int head[N], cnt;
void add(int u, int v, int w){
    e[++cnt] = (edge){v, w, head[u]};
    head[u] = cnt;
}
struct node{
    long long dis;
    int l;
    bool operator < (const node &b) const{
        return dis < b.dis;
    }
}stk1[N], stk2[N];
int sz[N], mx[N], maxn, dis[N], l[N], top1, top2;
bool vis[N];
void find(int u, int fa){
    sz[u] = 1, mx[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        find(v, u);
        sz[u] += sz[v];
        mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], maxn - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}
void dfs(int u, int fa){
    stk2[++top2] = (node){dis[u], l[u]};
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        dis[v] = max(dis[u], e[i].w), l[v] = l[u] + 1;
        dfs(v, u);
    }
}
void calc(int u){
    top1 = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        top2 = 0, dis[v] = e[i].w, l[v] = 1;
        dfs(v, u);
        sort(stk2 + 1, stk2 + top2 + 1);
        for (int j = 1; j <= top2; j++){
            ans -= ((R - stk2[j].l + 1 <= 0 ? 0 : query(R - stk2[j].l + 1)) - (L - stk2[j].l + 1 <= 0 ? 0 : query(L - stk2[j].l))) * stk2[j].dis;
            modify(stk2[j].l + 1, 1);
        }
        for (int j = 1; j <= top2; j++){
            modify(stk2[j].l + 1, -1);
            stk1[++top1] = stk2[j];
        }
    }
    stk1[++top1] = (node){0, 0};
    sort(stk1 + 1, stk1 + top1 + 1);
    for (int i = 1; i <= top1; i++){
        ans += ((R - stk1[i].l + 1 <= 0 ? 0 : query(R - stk1[i].l + 1)) - (L - stk1[i].l + 1 <= 0 ? 0 : query(L - stk1[i].l))) * stk1[i].dis;
        modify(stk1[i].l + 1, 1);
    }
    for (int i = 1; i <= top1; i++) modify(stk1[i].l + 1, -1);
}
void solve(int u){
    vis[u] = 1;
    calc(u);
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        maxn = sz[v];
        rt = 0;
        find(v, 0);
        solve(rt);
    }
}

int main(){
    n = read(), L = read(), R = read();
    for (int i = 1; i < n; i++){
        int u = read(), v = read(), w = read();
        add(u, v, w), add(v, u, w);
    }
    maxn = mx[rt] = n;
    find(1, 0);
    solve(rt);
    cout << (ans << 1);
    return 0;
}

P2634 [国家集训队] 聪聪可可

思路

这是一道点分治板题，但也能够从中获得启发，做法：将和 \(mod\) \(3\) 的余数用桶数组记录下来，再更新答案即可。

分数约分就用 \(\gcd\) 就行了。

代码

#include<iostream>
#define int long long

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 2e4 + 10;
int n, rt, ans1, ans2;
struct edge{
    int v, w, nxt;
}e[N << 1];
int head[N], cnt;
void add(int u, int v, int w){
    e[++cnt] = (edge){v, w, head[u]};
    head[u] = cnt;
}
int sz[N], mx[N], maxn, dis[N], stk1[N], top1, stk2[N], top2, ton[4];
bool vis[N];
void find(int u, int fa){
    sz[u] = 1, mx[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        find(v, u);
        sz[u] += sz[v];
        mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], maxn - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}
void dfs(int u, int fa){
    stk2[++top2] = dis[u];
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        dis[v] = dis[u] + e[i].w;
        dfs(v, u);
    }
}
void calc(int u){
    top1 = 0, ton[0] = 1;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        top2 = 0, dis[v] = e[i].w;
        dfs(v, u);
        for (int j = 1; j <= top2; j++) ans1 += ton[(3 - stk2[j] % 3) % 3];
        for (int j = 1; j <= top2; j++) ton[stk2[j] % 3]++, stk1[++top1] = stk2[j];
    }
    for (int i = 1; i <= top1; i++) ton[stk1[i] % 3]--;
}
void solve(int u){
    vis[u] = 1;
    calc(u);
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        rt = 0;
        maxn = sz[v];
        find(v, 0);
        solve(rt);
    }
}
int gcd(int a, int b){
    return (b == 0 ? a : gcd(b, a % b));
}

signed main(){
    n = read();
    for (int i = 1; i < n; i++){
        int u = read(), v = read(), w = read();
        add(u, v, w), add(v, u, w);
    }
    maxn = mx[rt] = n;
    find(1, 0);
    solve(rt);
    ans1 = ans1 * 2 + n;
    ans2 = n * n;
    int g = gcd(ans1, ans2);
    cout << ans1 / g << '/' << ans2 / g;
    return 0;
}

P3714 [BJOI2017] 树的难题

思路

是一道超级难的点分治题，但是难的在于统计答案，而不是套用板子就行，在点分治中，一条链需要维护权值，边数，这个链到根的那条边的颜色，以及这是该子树内第几条链。

如何统计答案？对于一个根，将链到根的边的颜色排序，如果相同，按链的编号排序（即第几条链），开两课线段树，一颗线段树存相同颜色的权值最大值，另一棵存不同颜色的权值最大值，相同显然要减去当前颜色的权值，排序的作用是先处理同种颜色同个子树的链，由于后面的与前面会匹配，所以前面的可以不和后面的匹配。

代码

#include<iostream>
#include<climits>
#include<algorithm>
#include<cmath>
#define int long long

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 2e5 + 10;
int n, m, L, R, rt, ans = INT_MIN;
int c[N];
int t1[N << 2], t2[N << 2];
inline void pushup(int now, int t[]){
    t[now] = max(t[now << 1], t[now << 1 | 1]);
}
inline void build(int now, int l, int r, int t[]){
    if (l == r){
        t[now] = LLONG_MIN;
        return;
    }
    int mid = (l + r) >> 1;
    build(now << 1, l, mid, t);
    build(now << 1 | 1, mid + 1, r, t);
    pushup(now, t);
}
inline void modify(int now, int l, int r, int x, int k, int t[]){
    if (l == r){
        if (k == LLONG_MIN) t[now] = k;
        else t[now] = max(t[now], k);
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(now << 1, l, mid, x, k, t);
    else modify(now << 1 | 1, mid + 1, r, x, k, t);
    pushup(now, t);
}
inline int query(int now, int l, int r, int x, int y, int t[]){
    if (x <= l && r <= y) return t[now];
    int mid = (l + r) >> 1, res = LLONG_MIN;
    if (x <= mid) res = max(res, query(now << 1, l, mid, x, y, t));
    if (mid + 1 <= y) res = max(res, query(now << 1 | 1, mid + 1, r, x, y, t));
    return res;
}
struct edge{
    int v, w, col, nxt;
}e[N << 1];
int head[N], cnt;
inline void add(int u, int v, int w, int col){
    e[++cnt] = (edge){v, w, col, head[u]};
    head[u] = cnt;
}
struct node{
    int dis, l, c, id;
    bool operator < (const node &b) const{
        if (c != b.c) return c < b.c;
        return id < b.id;
    }
}stk[N];
int sz[N], mx[N], maxn, top, dis[N], l[N];
bool vis[N];
inline void find(int u, int fa){
    sz[u] = 1, mx[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        find(v, u);
        sz[u] += sz[v];
        mx[u] = max(mx[u], sz[v]);
    }
    mx[u] = max(mx[u], maxn - sz[u]);
    if (mx[u] < mx[rt]) rt = u;
}
inline void dfs(int u, int fa, int col, int last, int id){
    stk[++top] = (node){dis[u], l[u], col, id};
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        if (e[i].col != last) dis[v] = dis[u] + e[i].w;
        else dis[v] = dis[u];
        l[v] = l[u] + 1;
        dfs(v, u, col, e[i].col, id);
    }
}
inline void calc(int u){
    top = 0;
    int id = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        dis[v] = e[i].w, l[v] = 1;
        dfs(v, u, e[i].col, e[i].col, ++id);
    }
    sort(stk + 1, stk + top + 1);
    build(1, 1, top + 1, t1);
    build(1, 1, top + 1, t2);
    modify(1, 1, top + 1, 1, 0, t2);
    int l = 1, r = 1;
    for (int i = 1; i <= top; i++){
        if (stk[i].id != stk[i - 1].id && i != 1){
            if (stk[i].c == stk[i - 1].c){
                for (int j = l; j <= r; j++) modify(1, 1, top + 1, stk[j].l + 1, stk[j].dis, t1);
            }else{
                for (int j = l; j <= r; j++) modify(1, 1, top + 1, stk[j].l + 1, LLONG_MIN, t1), modify(1, 1, top + 1, stk[j].l + 1, stk[j].dis, t2);
            }
            l = r = i;
        }else r = i;
        if (min(R - stk[i].l, R) + 1 <= 0) continue;
        int x = query(1, 1, top + 1, max(min(L - stk[i].l, top) + 1, 1ll), max(min(R - stk[i].l, top) + 1, 1ll), t1);
        int y = query(1, 1, top + 1, max(min(L - stk[i].l, top) + 1, 1ll), max(min(R - stk[i].l, top) + 1, 1ll), t2);
        if (x != LLONG_MIN) ans = max(ans, x - c[stk[i].c] + stk[i].dis);
        if (y != LLONG_MIN) ans = max(ans, y + stk[i].dis);
    }
    
}
inline void solve(int u){
    vis[u] = 1;
    calc(u);
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (vis[v]) continue;
        rt = 0;
        maxn = sz[v];
        find(v, 0);
        solve(rt);
    }
}

signed main(){
    n = read(), m = read(), L = read(), R = read();
    for (int i = 1; i <= m; i++) c[i] = read();
    for (int i = 1; i < n; i++){
        int u = read(), v = read(), col = read(), w = c[col];
        add(u, v, w, col), add(v, u, w, col);
    }
    maxn = mx[rt] = n;
    find(1, 0);
    solve(rt);
    cout << ans;
    return 0;
}

标签：rt,10,int,分治,read,include,getchar
From： https://www.cnblogs.com/bryceyyds/p/18369778

相关文章

  • 经典分治算法
    RT，主要介绍一些经典的分治算法CDQ分治经典人类智慧算法。三维偏序问题三维偏序是CDQ分治的一个经典应用，搭配树状数组可以在\(O(n\log^2n)\)的时间复杂度内解决问题。如果我们枚举每一个元素，然后枚举其他的元素的话，可以在\(O(n^2)\)的时间复杂度解决这个问题，但显然无法......
  • 【数据结构与算法】分治法
    分治法目录一.分治法的思想二.分治法的步骤三.举个例子四.具体实现五.完整代码一.分治法的思想将一个大问题,拆解成为若干个小问题,而且大问题与小问题的解决方法一样.说到这里我们可以联想到递归,没错就是用递归的思想.分:递归解决较小的问题治:子问题的解构建原......
  • Note - 树分治（点分治、点分树）
    陈年笔记，现在可能不会了。点分治Q1：基本思想是什么？将路径分为经过\(u\)和不经过\(u\)的两类，在每次分治中计算经过\(u\)的路径数量。Q2：如何统计？一般：遍历\(u\)的每个子节点\(v\)，把\(v\)子树内的节点记录下来，得到答案并更新数组。容斥：把\(u\)子树内的节点都记录下......
  • 根号分治莫队
    莫队参考文章：莫队细讲——从零开始学莫队莫队算法——从入门到黑题oiwiki--普通莫队莫队简介莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经Codeforces的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析......
  • 点分治
    点分治以树的重心为根，对子树内的问题分治求解，时间复杂度可以做到\(O(n\logn\timesF(n))\)，其中\(F(n)\)是解决经过根的问题所需要的处理。P3806模版给一棵有边权的树，多次询问树上是否存在距离为\(k\)的点对。\(n\le10^4,m\le100,k\le10^7\)假设现在\(rt\)是根，则......
  • 点分治
    参考博客概述点分治适合处理大规模的树上路径信息问题。——摘自OIWiki时间复杂度\(O(n\logn)\)（每次\(calc\)时间复杂度为\(O(size_{root})\)）。对于树上的所有路径及一个假定的根\(rt\)，有两种路径：经过\(rt\)的；不经过\(rt\)的。第一种路径显然分两部分（可以......
  • cdq分治
    我觉得呢，cdq的本质就是在归并排序消掉一维的影响来处理多维偏序问题。既然本质跟二分有关，那很容易猜到cdq处理k维偏序的时间复杂度为\(O(Nlog^{k-1}N)\)三维偏序问题：形如：$求满足条件a_i<a_j,b_i<b_j,c_i<c_j且\(j!=i\)的j个数比较常考的就是三维偏序，一般做法就是sort消掉一......
  • CDQ分治
    P3810【模板】三维偏序（陌上花开）CDQ模板题，考虑先按\(a\)排序，减掉一位，然后再\(CDQ\)分治一维，用树状数组维护最后一维还有本题特殊,去重操作不要忘记点击查看代码#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#definell......
  • CDQ分治
    CDQ分治的思想最早由IOI2008金牌得主陈丹琦在高中时整理并总结，它也因此得名。CDQ分治的思想常用于离线解决点对之间的问题，最经典的如三维偏序。解决这类问题的过程为：将序列$(l,r)$分为。递归处理序列$(l,mid)$和$(mid+1,r)$中的答案。设计算法处理......
  • cdq分治总结
    \(cdq\)分治是一种离线分治算法，可以将动态问题改变为静态问题，不适用于强制在线。其实现时通常将需要进行的操作存进一个结构体，然后对这些操作进行分治。打\(cdq\)分治时一个直观的感受就是很好想思路，但就是不知道怎么打。。。它一共有三个需要干的1找到范围中点\(mid\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99