让人不想看的题解

ok啊我们可以很轻松的知道这道题的意思是给你一个数组和一个目标数，让你找数组里两个数，加起来刚好等于目标数，然后返回它们的下标。直接想的话可能会想到用两层循环，但这样还是太吃时间复杂度了。还有没有更好用的方法呢，有的有的，兄弟有的，其实可以用个哈希表来优化！我们一边遍历数组，一边把每个数和它的下标存到哈希表里。每次都去查一下“目标数减去当前这个数”的差值有没有在哈希表里。如果找到了，直接返回差值的下标和当前下标就行。这样写又快又清楚，时间复杂度是O(n)，看起来还是很高效的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 50001;
int n, m, size, l, r, mid, tot1, tot2;
int first[maxn], num[maxn], f[maxn][18], d[maxn][18], p[maxn], vis[maxn];

struct bian {
    int to, next, len;
};
bian edge[maxn << 1];

struct shu {
    int id, len;
};
shu a[maxn], b[maxn];

int read() {
    int x = 0, f = 1;
    char c;
    for (c = getchar(); (!isdigit(c)) && (c != '-'); c = getchar());
    if (c == '-') f = -1, c = getchar();
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    return x * f;
}

void build(int x, int y, int z) {
    edge[++size].next = first[x];
    first[x] = size;
    edge[size].to = y;
    edge[size].len = z;
}

void dfs(int point, int fa) {
    for (int u = first[point]; u; u = edge[u].next) {
        int to = edge[u].to;
        if (to == fa) continue;
        f[to][0] = point;
        d[to][0] = edge[u].len;
        dfs(to, point);
    }
}

void pre() {
    for (int j = 1; j <= 16; j++) {
        for (int i = 1; i <= n; i++) {
            if (f[i][j - 1]) {
                f[i][j] = f[f[i][j - 1]][j - 1];
                d[i][j] = d[i][j - 1] + d[f[i][j - 1]][j - 1];
            }
        }
    }
}

inline void search(int point, int fa) {
    if (vis[point]) return;
    vis[point] = 1;
    int tag = 0;
    for (int u = first[point]; u; u = edge[u].next) {
        int to = edge[u].to;
        if (to == fa) continue;
        tag = 1;
        search(to, point);
        vis[point] &= vis[to];
    }
    if (!tag) vis[point] = 0;
}

bool comp(const shu &a, const shu &b) {
    return a.len < b.len;
}

bool check(int mid) {
    tot1 = tot2 = 0;
    for (int i = 1; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= m; i++) {
        int sum = 0, x = p[i];
        for (int k = 16; k >= 0; k--) {
            if (f[x][k] > 1 && sum + d[x][k] <= mid) {
                sum += d[x][k];
                x = f[x][k];
            }
        }
        if (f[x][0] == 1 && sum + d[x][0] <= mid) {
            a[++tot1].len = mid - sum - d[x][0];
            a[tot1].id = x;
        } else {
            vis[x] = 1;
        }
    }
    search(1, 0);
    if (vis[1]) return true;
    for (int u = first[1]; u; u = edge[u].next) {
        if (!vis[edge[u].to]) {
            b[++tot2].len = edge[u].len;
            b[tot2].id = edge[u].to;
        }
    }
    sort(a + 1, a + tot1 + 1, comp);
    sort(b + 1, b + tot2 + 1, comp);
    if (tot1 < tot2) return false;
    int tag = 1;
    for (int i = 1; i <= tot1; i++) {
        if (!vis[a[i].id]) vis[a[i].id] = 1;
        else if (a[i].len >= b[tag].len) vis[b[tag].id] = 1;
        while (tag <= tot2 && vis[b[tag].id]) tag++;
        if (tag > tot2) return true;
    }
    return tag > tot2;
}

int main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read(), z = read();
        build(x, y, z);
        build(y, x, z);
    }
    m = read();
    for (int i = 1; i <= m; i++) p[i] = read();
    dfs(1, 0);
    pre();
    l = 0, r = 1e9;
    int tag = 0;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            tag = 1;
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (tag) cout<< r << " ";
    else cout << "-1";
    return 0;
}