传送门：https://nanti.jisuanke.com/t/38229

题意

给n个点，n-1条边，每条边都有边权。
m此询问，输出u到v这条简单路径上边权<=k的边数。

思路

首先看到这道题，找到几个关键点。u到v、区间小于k的个数

• u到v的简单路径，可以树剖将树化为数列进行模拟.
• 区间<=k的个数，在树的dfs序上建主席树。

这题是边权，我们树剖完成之后，根据每个节点的深度，将边权给儿子作为点权。
根节点1就没有权值，所以我们将根节点的点权设为最大值，使主席树不影响。

然后根据dfs序，建n颗主席树，最后利用前缀和的思想，得出答案。

root[0]这棵初始主席树建不建无所谓，都ok。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

#define lc u << 1
#define rc u << 1 | 1
#define mid (t[u].l + t[u].r) / 2
#define INF 0x3f3f3f3f
#define lowbit(x) x & (-x)
#define mem(a, b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int maxn = 1e5 + 10;
const int N = 1e5 + 10;

/*-------------------建边-----------------*/

struct Edge {
    int v, next;
}e[maxn << 1];
int head[maxn << 1], t;
int eg[N << 1][3];

inline void add(int u, int v) {
    e[++t].v = v;
    e[t].next = head[u];
    head[u] = t;
}

/*-------------------轻重链剖分-----------------*/

int dep[N], siz[N], fa[N], son[N];

void dfs1(int u, int par) {
    dep[u] = dep[fa[u] = par] + (siz[u] = 1);
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == par) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(!son[u] || siz[v] > siz[son[u]])
            son[u] = v;
    }
}

int tim, dfn[N], nodeof[N], top[N];

void dfs2(int u, int topf) {
    nodeof[dfn[u] = ++tim] = u;
    top[u] = topf;
    if(!son[u]) return ;
    dfs2(son[u], topf);
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

/*-------------------树上主席树-----------------*/

int n, m;
int a[N];
vector<int> v;
int cnt, root[N];

struct Tree {
    int l, r;
    int sum;
}hjt[N * 40];

inline int getid(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; }

void build(int &now, int l , int r) {
    now = ++cnt;
    if(l == r) return ;
    int m = (l + r) >> 1;
    build(hjt[now].l, l, m);
    build(hjt[now].r, m + 1, r);
}

void insert(int pre, int &now, int l, int r, int p) {
    hjt[now = ++cnt] = hjt[pre];
    hjt[now].sum++;
    if(l == r) {
        return ;
    }
    int m = (l + r) >> 1;
    if(p <= m) insert(hjt[pre].l, hjt[now].l, l, m, p);
    else insert(hjt[pre].r, hjt[now].r, m + 1, r, p);
}

int query(int L, int R, int l, int r, int k) {
    if(l == r) return hjt[R].sum - hjt[L].sum;
    int m = (l + r) >> 1;

    int ans = 0;
    if(k <= m) ans += query(hjt[L].l, hjt[R].l, l, m, k);
    else {
        ans += hjt[hjt[R].l].sum - hjt[hjt[L].l].sum;
        ans += query(hjt[L].r, hjt[R].r, m + 1, r, k);
    }
    return ans;
}

int query_chain(int x, int y, int k) {
    int ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query(root[dfn[top[x]] - 1], root[dfn[x]], 1, n, k);
        x = fa[top[x]];
    }
    if(x == y) return ans;
    if(dep[x] > dep[y]) swap(x, y);
    ans += query(root[dfn[x]], root[dfn[y]], 1, n, k);
    return ans;
}

void solve() {
    scanf("%d%d",&n,&m);
    // 剖分
    for(int i = 1;i < n; i++) {
        int u, v, w;
        scanf("%d%d%d",&u,&v,&w);
        add(u, v);
        add(v, u);
        eg[i][0] = u; eg[i][1] = v; eg[i][2] = w;
    }
    dfs1(1, 0);
    dfs2(1, 1);
    // 建树
    for(int i = 1;i < n; i++) {
        if(dep[eg[i][0]] > dep[eg[i][1]]) swap(eg[i][0], eg[i][1]);
        a[eg[i][1]] = eg[i][2];
        v.push_back(eg[i][2]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    build(root[0], 1, n);
    for(int i = 1;i <= n; i++) {
        int x = getid(a[nodeof[i]]);
        if(i == 1) x = n + 1;
        insert(root[i - 1], root[i], 1, n, x);
    }
    // 查询
    while(m--) {
        int l, r, k;
        scanf("%d%d%d",&l,&r,&k);
        k = upper_bound(v.begin(), v.end(), k) - v.begin() + 1; // 第一个比k大于等于的数的下标
        k--;
        if(k == 0) {
            printf("0\n");
            continue;
        }
        printf("%d\n",query_chain(l, r, k));
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
#ifdef FZT_ACM_LOCAL
//    int size=40<<20;
//    __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
#else
    solve();
#endif
    return 0;
}