由于一些琐事，很长时间没有更新博客了……尽管做了不少题，但还是给我些时间整理思绪吧……

大方向肯定是点分治没错啦……

点分治的题处理经过根的路径通常有两种套路……一种是类似BZOJ 1468那样，收集所有儿子的信息，然后一次性合并，并排除不合法的情况。另一种类似于这道题，顺次处理儿子的信息，处理一个合并一个。

具体的思路是，用[tex]p[x][/tex]表示目前已知的所有从根开始长度为[tex]x[/tex]的路径（当然根本身也算上啦，所以说一开始就把[tex]p[root][/tex]设为0），然后根搜集信息时每次对一个儿子进行DFS，假设某结点[tex]x[/tex]到根的距离为[tex]d[x][/tex]，那么显然[tex]x[/tex]对答案的贡献为[tex]p[k-d[x]][/tex]，之后把这个子树合并到[tex]p[/tex]中。

注意清理[tex]p[/tex]的时候不能直接暴力memset……这样会被卡常致死。更好的方法是对于每次把子树合并到[tex]p[/tex]中时，把[tex]x[/tex]记录下来，然后清理[tex]p[/tex]时常数就小很多了。

代码：

/**************************************************************
    Problem: 2599
    User: danihao123
    Language: C++
    Result: Accepted
    Time:14640 ms
    Memory:23532 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 200005;
const int maxm = maxn * 2;
const int maxk = 1000005;
struct Edge {
    Edge *next;
    int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
    graph_cnt = 0;
    memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
    Edge *e = &pool[graph_cnt++];
    e->next = first[u];
    first[u] = e;
    e->to = v;
    e->dist = d;
}
 
int k;
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
    siz[x] = 1;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_siz(v, x);
            siz[x] += siz[v];
        }
    }
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
    bool OK = siz[x]*2 >= siz[now_root];
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_best_root(v, x);
            OK = OK && (siz[v]*2 <= siz[now_root]);
        }
    }
    if(OK) {
        best_root = x;
    }
}
int buf[maxk];
int ans;
void deal_ans(int x, int fa, int dep, int d) {
    if(d > k) {
        return;
    }
    ans = min(ans, dep + buf[k-d]);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            deal_ans(v, x, dep + 1, d + e->dist);
        }
    }
}
void add_to_buf(int x, int fa, int dep, int d) {
    if(d > k) {
        return;
    }
    buf[d] = min(buf[d], dep);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            add_to_buf(v, x, dep + 1, d + e->dist);
        }
    }
}
void clear_buf(int x, int fa, int dep, int d) {
    if(d > k) {
        return;
    }
    buf[d] = 0x3f3f3f3f;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            clear_buf(v, x, dep + 1, d + e->dist);
        }
    }
}
void divide(int x) {
    gen_siz(x, 0);
    now_root = best_root = x; gen_best_root(x, 0);
    x = best_root;
    vis[x] = true;
    buf[0] = 0;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v]) {
            deal_ans(v, x, 1, e->dist);
            add_to_buf(v, x, 1, e->dist);
        }
    }
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v]) {
            clear_buf(v, x, 1, e->dist);
        }
    }
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v]) {
            divide(v);
        }
    }
}
inline int readint() {
    int x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}
 
int main() {
    int n;
    n = readint();
    k = readint();
    clear_graph();
    for(int i = 1; i <= (n-1); i++) {
        int u, v, d;
        u = readint();
        v = readint();
        d = readint();
        u++; v++;
        add_edge(u, v, d);
        add_edge(v, u, d);
    }
    ans = 0x3f3f3f3f;
    memset(buf, 0x3f, sizeof buf);
    divide(1);
    if(ans == 0x3f3f3f3f) {
        ans = -1;
    }
    printf("%d\n", ans);
    return 0;
}

• 相关文章
• 全局相关文章