BZOJ 1316: 树上的询问 – [点分治][模版]

题目传送门(BZOJ)
>原文链接<

题解 :

​ 点分治模版题。我们只简单的讲一下点分治的思路 。

序列分治 :

​ 我们把整个序从某个点分成两部分,然后统计跨过这个点的答案,然后递归两个区间求解。

点分治也一样, 我们把树按某个点分成几个部分,先统计经过这个点的路径, 然后递归各棵子树。
经过这个点的路径就是由属于这个两个不同子树中的点构成点对的路径

pic

而其中 A\to B 即为 A\to P + P\to B 所以对于 P 我们把子树中到它的路径预处理出来,然后一起统计。

分治中心

序列分治时,我们常常选择区间中点为分治中心,每次使区间长度除以2,这样保证最多有 \log n 层,点分治同样也需要选取一个优秀的分治中心,来保证时间复杂度。

一般来讲选择重心作为分治中心,因为这使得子树大小不会超过 \frac{N}{2} 有一个类似于启发式合并的复杂度。这里不做证明。

重心如何求 ?

void getRoot(int p, int fa) {
    f[p] = 0, siz[p] = 1; // f[p] : 选取当前点为重心,最大子树的点数
    rev(i, p) { // 遍历邻接表
        if(i->to != fa && !vis[i->to]) { // 把分治中心删掉,不能遍历回去 (vis[])
            getRoot(i->to, p); // 递归处理 siz
            siz[p] += siz[i->to];
            f[p] = std :: max(f[p], siz[i->to]);
        }
    }
    f[p] = std :: max(f[p], tmp - siz[p]); // tmp 是当前分治部分的 siz大小
    if(f[p] < f[root]) root = p;  
}

如何预处理路径 ?

void getDis(int p, int fa) {
    a[++*a] = dis[p];
    rev(i, p) {
        if(i->to != fa && !vis[i->to]) {
            dis[i->to] = dis[p]+i->val;
            getDis(i->to, p);
        }
    }
}

预处理之后的计算 :

inline void calc(int p, int c) { // c 是为了方便容斥
    *a = 0;
    getDis(p, 0);
    for(int i = 1; i <= *a; i ++ )
    for(int j = i+1; j <= *a; j ++ )
    if(a[i]+a[j] <= 10000000) hav[a[i]+a[j]] += c; // hav[] 是个桶,储存是否有这么长的路径
}

而这样的计算会产生重复,所以我们分治中心加,递归部分要单步容斥减掉。

代码 :(然而是洛谷的那个模版,不能直接过1316)

#include 
#include 
#include 
#define ll long long
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
const int N = 41000;
char buf[100000],*p1,*p2;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48), ch = nc();
    return x;
}
struct Edge {
    int to, val;
    Edge *next;
}*h[N],e[N<<1];
inline void Add_Edge(int u, int v, int w) {
    static int _ = 0;
    Edge *tmp = &e[++_];
    tmp->to = v;
    tmp->val = w;
    tmp->next = h[u];
    h[u] = tmp;
}
int n, siz[N], f[N], root, K, tmp;
ll dis[N], a[N], ans;
int hav[10010000];
bool vis[N];
void getRoot(int p, int fa) {
    f[p] = 0, siz[p] = 1;
    rev(i, p) {
        if(i->to != fa && !vis[i->to]) {
            getRoot(i->to, p);
            siz[p] += siz[i->to];
            f[p] = std :: max(f[p], siz[i->to]);
        }
    }
    f[p] = std :: max(f[p], tmp - siz[p]);
    if(f[p] < f[root]) root = p;  
}
void getDis(int p, int fa) {
    a[++*a] = dis[p];
    rev(i, p) {
        if(i->to != fa && !vis[i->to]) {
            dis[i->to] = dis[p]+i->val;
            getDis(i->to, p);
        }
    }
}
inline void calc(int p, int c) {
    *a = 0;
    getDis(p, 0);
    for(int i = 1; i <= *a; i ++ )
    for(int j = i+1; j <= *a; j ++ )
    if(a[i]+a[j] <= 10000000) hav[a[i]+a[j]] += c;
}
void dfs(int p) {
    dis[p] = 0, vis[p] = true;
    calc(p, 1);
    rev(i, p) {
        if(!vis[i->to]) {
            dis[i->to] = i->val;
            calc(i->to, -1);
            tmp = siz[i->to];
            root = 0;
            getRoot(i->to, p);
            dfs(root);
        }
    }
}
int main() {
    tmp = n = rd(); int m = rd();
    for(int i = 2; i <= n; i ++ ) {
        int u = rd(), v = rd(), w = rd(); 
        Add_Edge(u, v, w), 
        Add_Edge(v, u, w);
    }
    *f = 1<<30;
    getRoot(1, 0);
    dfs(root);
    while(m -- ) {
        K = rd();
        puts(hav[K] ? "AYE" : "NAY");
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注