点分治第一题……

这个也就是最经典的那个点分治问题了吧……参照qzc大爷的论文吧。

代码：

/**************************************************************
    Problem: 1468
    User: danihao123
    Language: C++
    Result: Accepted
    Time:816 ms
    Memory:2736 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 40005;
const int maxm = maxn * 2;
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;
int calc(vector<int>& V) {
    int size = V.size();
    int rc = size - 1;
    int ans = 0;
    if(size <= 1){
        return 0;
    }
    for(int i = 0; i < size; i++) {
        while(i < rc && V[i] + V[rc] > k) {
            rc--;
        }
        if(i == rc) {
            break;
        }
        ans += rc - i;
    }
    return ans;
}
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;
    }
}
void add_to_V(int x, int fa, int d, vector<int>& V) {
    V.push_back(d);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            add_to_V(v, x, d + e->dist, V);
        }
    }
}
int divide(int x) {
    gen_siz(x, 0);
    now_root = x;
    gen_best_root(x, 0);
    x = best_root;
    vis[x] = true;
    vector<int> V, CV;
    int ans = 0;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(vis[v]) {
            continue;
        }
        CV.clear();
        add_to_V(v, x, e->dist, CV);
        sort(CV.begin(), CV.end());
        ans -= calc(CV);
        for(int i = 0; i < CV.size(); i++) {
            V.push_back(CV[i]);
        }
    }
    V.push_back(0);
    sort(V.begin(), V.end());
    ans += calc(V);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(vis[v]) {
            continue;
        }
        ans += divide(v);
    }
    return ans;
}
 
int main() {
    int n;
    scanf("%d", &n);
    clear_graph();
    for(int i = 1; i <= (n - 1); i++) {
        int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        add_edge(u, v, d);
        add_edge(v, u, d);
    }
    scanf("%d", &k);
    printf("%d\n", divide(1));
    return 0;
}

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