Luogu 4178 Tree

题解

解

题意同 Poj 1741
接下来给出两份代码

Code 1

#include <bits/stdc++.h>
const int N = 4e4 + 10;
const int oo = 1e9;
struct Node {int v, w, nxt;} G[N << 1];
int n, k, now = 1, head[N];
int size[N], maxson[N], dis[N];
bool vis[N];
int Max, Root, tot, Size;
int Answer;
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
inline void Add(int u, int v, int w) {G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;}
void Getroot(int u, int fa) {
    size[u] = 1;
    maxson[u] = 0;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v] && v != fa) {
            Getroot(v, u);
            size[u] += size[v];
            maxson[u] = std:: max(maxson[u], size[v]);
        }
    }
    maxson[u] = std:: max(maxson[u], Size - size[u]);
    if(maxson[u] < Max) {Max = maxson[u]; Root = u;}
}
void Getdis(int u, int fa, int len) {
    dis[++ tot] = len;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v] && v != fa) Getdis(v, u, len + G[i].w);
    }
}
int Calc(int u, int len) {
    tot = 0;
    for(int i = 1; i <= n; i ++) dis[i] = 0;
    Getdis(u, 0, len);
    std:: sort(dis + 1, dis + tot + 1);
    int L = 1, R = tot, ret(0);
    while(L <= R) {
        if(dis[L] + dis[R] <= k) ret += (R - L), L ++;
        else R --;
    }
    return ret;
}
void Getans(int u) {
    Answer += Calc(u, 0);
    vis[u] = 1;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v]) {
            Answer -= Calc(v, G[i].w);
            Size = size[v];
            Max = oo;
            Getroot(v, 0);
            Getans(Root);
        }
    }
    return ;
} 
int main() {
    n = read();
    now = 1;
    for(int i = 1; i <= n; ++ i) head[i] = -1, vis[i] = 0;
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read(), w = read();
        Add(u, v, w), Add(v, u, w);
    }
    k = read();
    Answer = 0;
    Max = oo;
    Size = n;
    Getroot(1, 0);
    Getans(Root);
    std:: cout << Answer << "\n";
    return 0;
}

Code 2

#include <bits/stdc++.h>
const int N = 4e4 + 10;
const int oo = 1e9;
struct Node {int v, w, nxt;} G[N << 1];
int n, k, now = 1, head[N];
int size[N], maxson[N], dis[N];
bool vis[N];
int Max, Root, tot, Size;
int Answer;
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
inline void Add(int u, int v, int w) {G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;}
void Getroot(int u, int fa) {
    size[u] = 1;
    maxson[u] = 0;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(vis[v] || v == fa) continue ;
        Getroot(v, u);
        size[u] += size[v];
        maxson[u] = std:: max(maxson[u], size[v]);
    }
    maxson[u] = std:: max(maxson[u], n - size[u]);
    if(maxson[u] < maxson[Root]) Root = u;
}
void Getdis(int u, int fa, int len) {
    dis[++ tot] = len;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(vis[v] || v == fa) continue ;
        Getdis(v, u, len + G[i].w);
    }
}
int Calc(int u, int len) {
    tot = 0;
    Getdis(u, 0, len);
    std:: sort(dis + 1, dis + tot + 1);
    int L = 1, R = tot, ret(0);
    while(L <= R) {
        while(dis[L] + dis[R] > k && R > L) R --;
        ret += R - L;
        L ++; 
    }
    return ret;
}
void Getans(int u) {
    Answer += Calc(u, 0);
    vis[u] = 1;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(!vis[v]) {
            Answer -= Calc(v, G[i].w);
            Root = 0;
            Getroot(v, 0);
            Getans(Root);
        }
    }
    return ;
} 
int main() {
    n = read();
    now = 1;
    for(int i = 1; i <= n; ++ i) head[i] = -1, vis[i] = 0;
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read(), w = read();
        Add(u, v, w), Add(v, u, w);
    }
    k = read();
    Root = 0;
    maxson[Root] = n;
    Getroot(1, 0);
    Getans(Root);
    printf("%d\n", Answer);
    return 0;
}

在Luogu Code1 会TLE 6 个测试点， Code2 可以 AC

代码不同之处

Code 1 在递归子树时，将树的大小看成整棵树的大小
其他没有什么太大区别
why???