Fall 2019 ICPC-style Waterloo Local Contest，D

谨以此博文，纪念 L_fire 的逝去，L_ndyz 的诞生。

一篇博文需要一张头图：

Fall 2019 ICPC-style Waterloo Local Contest，D

ICPC 的题啊，还是 D 题啊，果然不简单（

Link

Background

集训的时候 Ptilopsis_w 找我，让我去找 wljss，说让 wljss 看他的私信。

然后我就去了，强行阻止了正在玩游戏的 wljss，跟他说 Ptilopsis_w 找他。

然后我对于他们的聊天内容产生了兴趣，于是我回去问 Ptilopsis_w 他们说了什么。

然后 Ptilopsis_w 说 wljss 昨天给了他一个题，他 yy 了一个做法给他看。

我表示想看看那个题，然后……

然后我的噩梦就开始了。

后边……疯狂地想，要用的东西倒是想的差不多了。

但是呢，很多细节都没有想出来（太菜了），然后跑去找 Sunny_r，学会之后开始写，一写就 5kb，然后找 Sunny_r 调，被 Sunny_r 痛击了 n 下（真·物理攻击）之后终于切掉了此题。

这叫什么？这就叫做身心俱疲（

Sunny_r：Shelter_Prime 他还是挺乖巧的结果老是挨揍。

Analysis

这题其实很简单，你只需要学会树剖，离线操作，线段树，数论分块就可以做了！

我们把题意简化一下：

给一棵 $n$ 个点的树，边权 $w_i$，有 $q$ 次询问，每次询问如 $s,t,x$，求 $\sum _{i \in path(s,t)} \lceil \frac{w_i}{x} \rceil$

最后的答案加 1。

我相信肯定有人上来直接一手区间和再除以给定的 x 的，但是这破绽也太明显了……

很明显的：ceil(1 / 3) + ceil(2 / 3) ≠ ceil(3 / 3)

不好做啊（

我们观察一下这个式子，我们是不是发现这跟数论函数蛮像的？

那我们是不是发现，这是隔一段数才会发生变化的？

欸？

又发现这个 x 才只有 2e4？

那我们是不是就可以来一手数论分块求一下对于除以一个数，会造成值改变的那些数都有什么？

但是发现树上的权值可能重复，于是我们记录一下一个权值对应的下放后的 dfn 值。

然后发现在线不好回答，于是我们直接一手离线，通过枚举 x，独立地修改线段树上的权值，然后直接统计和是不是就可以了？

离线之后要按 x 升序排序！

这里的修改是单点修改。

然后如果当前的 x 跟我们当前的询问对上了，我们就可以直接统计下答案输出就可以了。

Code

// link: https://codeforces.com/gym/102367/problem/D
// Author: Shelter Prime
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

ll rd() {
    ll x = 0, w = 1;
    char c = getchar();
    
    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }
    
    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    
    return x * w;
}

const int N = 1e5 + 5;

int n, m;

struct Graph {
    int v, nxt;
    ll w;
}e[N << 1];

int lk[N], ltp;

void ins(int u, int v, ll w) {
    e[++ltp] = {v, lk[u], w};
    lk[u] = ltp;
}

int dep[N], fa[N], son[N], siz[N];
int top[N], dfn[N], rk[N];
int num;
ll ans[N];
ll a[N];

vector <int> numb[N]; // 在 i 这个值下会发生改变的数
vector <int> val[N]; // 会发生数改变的 dfn 值

struct Ask {
    int id;
    int u, v;
    ll x;
}q[N];

void init() {
    for(int i = 1; i <= 20000; ++i) { // 考虑当前的被除数
        for(int l = 1, r; l <= 20000; l = r + 1) {
            if((ll)ceil(1.0 * i / l) == 1) {
                numb[l].push_back(i);
                break;
            }
            else {
                numb[l].push_back(i);
                r = ceil(1.0 * i / (ceil(1.0 * i / l) - 1)) - 1;
            }
        }
    }
}

bool cmp(Ask x, Ask y) {
    return x.x < y.x;
}

void dfs1(int u) {
    siz[u] = 1, son[u] = -1;
    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dep[v]) {
            fa[v] = u;
            dep[v] = dep[u] + 1;
            a[v] = e[i].w;
            dfs1(v);
            siz[u] += siz[v];
            if(son[u] == -1 || siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++num;
    rk[num] = u;
    val[a[u]].push_back(dfn[u]);
    
    if(son[u] == -1) return ;
    
    dfs2(son[u], t);
    
    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(v != fa[u] && v != son[u])
            dfs2(v, v);
    }
}

struct Tree {
    int l, r;
    ll dat;
    
    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define dat(x) tr[x].dat
    #define ls (p << 1)
    #define rs (ls | 1)
    
}tr[N << 2];

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if(l == r) {
        dat(p) = a[rk[l]];
        return ;
    }
    
    int mid = (l + r) >> 1;
    
    build(ls, l, mid);
    build(rs, mid + 1, r);
    
    dat(p) = dat(ls) + dat(rs);
}

void change(int p, int l, int r, int delta) {
    if(l <= l(p) && r >= r(p)) {
        dat(p) = delta;
        return ;
    }
    
    int mid = (l(p) + r(p)) >> 1;
    
    if(l <= mid) change(ls, l, r, delta);
    if(r > mid) change(rs, l, r, delta);
    
    dat(p) = dat(ls) + dat(rs);
}

ll ask(int p, int l, int r) {
    if(l <= l(p) && r >= r(p)) return dat(p);
    
    ll res = 0;
    int mid = (l(p) + r(p)) >> 1;
    
    if(l <= mid) res += ask(ls, l, r);
    if(r > mid) res += ask(rs, l, r);
    
    return res;
}

ll aask(int u, int v) {
    ll res = 0;
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
            res += ask(1, dfn[top[u]], dfn[u]);
            u = fa[top[u]];
        }

    if(dep[u] > dep[v]) swap(u, v);
    res += ask(1, dfn[u] + 1, dfn[v]);
    
    return res;
}

int main() {
    n = rd(), m = rd();
    
    for(int i = 1; i < n; ++i) {
        int u = rd(), v = rd();
        ll w = rd();
        ins(u, v, w);
        ins(v, u, w);
    }
    
    dep[1] = 1;
    dfs1(1);
    dfs2(1, 1);
    init();
    build(1, 1, n);
    
    // print(1, 1, n);
    
    for(int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        ll x = rd();
        
        q[i].id = i, q[i].u = u, q[i].v = v;
        q[i].x = x;
    }
    
    sort(q + 1, q + 1 + m, cmp);
    
    int cnt = 1;
    
    for(int x = 1; x <= q[m].x; ++x) {
        for(int i = 0; i < numb[x].size(); ++i) {
            for(int j = 0; j < val[numb[x][i]].size(); ++j)
                change(1, val[numb[x][i]][j], val[numb[x][i]][j], ceil(numb[x][i] * 1.0 / x));
        }
        
        while(x == q[cnt].x) {
            int u = q[cnt].u, v = q[cnt].v;
            ll res = aask(u, v);
            
            ans[q[cnt].id] = res;
            ++cnt;
        }
    }
    
    for(int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i] + 1);
    
    return 0;
}

花絮

Sunny_r：“我对码不对人。”

Sunny_r：“你的学长学姐都是好人，只是偶尔脾气暴躁而已。”

我：“偶尔？”

Sunny_r：“……”