BZOJ2599【IOI2011】Race <点分治>

Problem

【IOI2011】Race

$\mathrm{Time\;Limit:\;70\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给一棵树,每条边有权.求一条简单路径,权值和等于$K$,且边的数量最小.$N\le 2\times 10^5$, $K\le 10^6$

Input

第一行 两个整数 $n, k$
第二至$n$行 每行三个整数，表示一条无向边的两端和权值 (注意点的编号从$0$开始)

Output

一个整数 表示最小边数量，如果不存在这样的路径，输出$-1$

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

2

标签：点分治

Solution

$\mathrm{OI}$生涯的第一道$\mathrm{IOI}$题（虽然是水题）
挺有意思的一道点分治题，把模板稍加变化即可。

用$mi[]$记录每种距离的路径长度的最小值，即$mi[i]$记录距离为$i$的路径的长度的最小值。
对于每个点，枚举其所有子结点。当枚举到子结点$v_k$时，将$v_k$的深度加上$v_1\sim v_k-1$中子结点的深度来更新$mi$数组。计算答案并和$ans$打擂。
注意在每个点计算答案时$mi$值需要重新计算，但此题常数较大，最好不要memset，可以再$mathrm{DFS}$一次撤销。

Code

#include <bits/stdc++.h>
#define MAX_N 200000
#define MAX_L 1000000
using namespace std;
int n, k, tot, rt, ans;
vector <int> G[MAX_N+5], E[MAX_N+5];
int s[MAX_N+5], h[MAX_N+5], dis[MAX_N+5], dep[MAX_N+5], mi[MAX_L+5];
bool mrk[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void getrt(int u, int fa) {
    s[u] = 1, h[u] = 0;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];	if (v == fa || mrk[v]) continue;
        getrt(v, u);	s[u] += s[v], h[u] = max(h[u], s[v]);
    }
    h[u] = max(h[u], tot-s[u]);
    if (h[u] < h[rt])	rt = u;
}
void calc(int u, int fa) {
    if (dis[u] <= k)	ans = min(ans, dep[u]+mi[k-dis[u]]);
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];	if (v == fa || mrk[v]) continue;
        dep[v] = dep[u]+1, dis[v] = dis[u]+c, calc(v, u);
    }
}
void upd(int u, int fa) {
    if (dis[u] <= k)	mi[dis[u]] = min(mi[dis[u]], dep[u]);
    for (int i = 0; i < (int)G[u].size(); i++)
        if (G[u][i] != fa && !mrk[G[u][i]])	upd(G[u][i], u);
}
void clr(int u, int fa) {
    if (dis[u] <= k)	mi[dis[u]] = n;
    for (int i = 0; i < (int)G[u].size(); i++)
        if (G[u][i] != fa && !mrk[G[u][i]])	clr(G[u][i], u);
}
void DFS(int u) {
    mi[0] = 0, mrk[u] = true;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];	if (mrk[v]) continue;
        dep[v] = 1, dis[v] = c, calc(v, 0), upd(v, 0);
    }
    for (int i = 0; i < (int)G[u].size(); i++)
        if (!mrk[G[u][i]])	clr(G[u][i], 0);
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];	if (mrk[v]) continue;
        rt = 0, tot = s[v], getrt(v, 0), DFS(rt);
    }
}
int main() {
    scanf("%d%d", &n, &k);	for (int i = 1, u, v, c; i < n; i++) scanf("%d%d%d", &u, &v, &c), u++, v++, addedge(u, v, c), addedge(v, u, c);
    for (int i = 1; i <= k; i++) mi[i] = n;	ans = tot = h[0] = n, getrt(1, 0), DFS(rt);	printf("%d", ans == n ? -1 : ans);
    return 0;
}