题目

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

输入格式

第一行 两个整数 n, k

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

输出格式

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

输入样例

4 3

0 1 1

1 2 2

1 3 4

输出样例

2

提示

2018.1.3新加数据一组，未重测

题解

比较常规的点分治，然而我还是因为不熟练写漏一个判定T得停不下来QAQ

每次找重心，遍历子树维护H数组H[i]表示离根i距离经过的最少边，每次遍历完一个子树，先查询一遍H数组更新答案，再更新H数组，保证不会出现在同一个子树中的情况

遍历完之后，再遍历一遍，把H数组还原【别memset，会T，因为每一层的节点数是不同的，才使得复杂度降低为O(nlogn)，而使用memset使得每一层操作都达到n】

之后往下找重心递归

搞完啦~~

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

using namespace std;

const int maxn = 200005,maxm = 1000005,INF = 1000000000;

inline int read(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}

    return out * flag;

}

int N,K,h[maxn],ne = 2;

struct EDGE{int to,nxt,w;}ed[2 * maxn];

inline void build(int u,int v,int w){

    ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++;

    ed[ne] = (EDGE){u,h[v],w}; h[v] = ne++;

}

int F[maxn],rt,Siz[maxn],vis[maxn],sum;

void getRT(int u,int fa){

    Siz[u] = 1; F[u] = 0;

    Redge(u) if (!vis[to = ed[k].to] && to != fa){

        getRT(to,u);

        Siz[u] += Siz[to];

        F[u] = max(F[u],Siz[to]);

    }

    F[u] = max(F[u],sum - Siz[u]);

    if (F[u] < F[rt]) rt = u;

}

int Dis[maxn],Len[maxn],di = 0,Hd[maxm],dis[maxn],dep[maxn],ansL = INF;

void cal(int u,int fa){

    if (dis[u] > K) return;

    Dis[++di] = dis[u]; Len[di] = dep[u];

    Redge(u) if (!vis[to = ed[k].to] && to != fa){

        dis[to] = dis[u] + ed[k].w;

        dep[to] = dep[u] + 1;

        cal(to,u);

    }

}

void solve(int u){

    vis[u] = true; Hd[0] = 0;

    Redge(u) if (!vis[to = ed[k].to]){

        di = 0; dis[to] = ed[k].w; dep[to] = 1;

        cal(to,u);

        REP(i,di) if (Hd[K - Dis[i]] + Len[i] < ansL)

            ansL = Hd[K - Dis[i]] + Len[i];

        REP(i,di) if (Hd[Dis[i]] > Len[i])

            Hd[Dis[i]] = Len[i];

    }

    Redge(u) if (!vis[to = ed[k].to]){

        di = 0; dis[to] = ed[k].w; dep[to] = 1;

        cal(to,u);

        REP(i,di) Hd[Dis[i]] = INF;

    }

    Hd[0] = INF;

    Redge(u) if (!vis[to = ed[k].to]){

        sum = Siz[to]; F[rt = 0] = INF;

        getRT(to,u);

        solve(rt);

    }

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out1.txt","w",stdout);

    N = read(); K = read(); int u,v,w;

    for (int i = 0; i < maxm; i++) Hd[i] = INF;

    REP(i,N - 1) u = read() + 1,v = read() + 1,w = read(),build(u,v,w);

    F[rt = 0] = INF; sum = N;

    getRT(1,0);

    solve(rt);

    if (ansL == INF) printf("-1\n");

    else printf("%d\n",ansL);

    return 0;

}