首页 > 其他分享 >P4149 [IOI2011] Race——点分治 模板

P4149 [IOI2011] Race——点分治 模板

时间:2024-11-05 21:58:40浏览次数:3  
标签:int IOI2011 样例 leq Race P4149 100

[IOI2011] Race

题目描述

给一棵树,每条边有权。求一条简单路径,权值和等于 \(k\),且边的数量最小。

输入格式

第一行包含两个整数 \(n,k\),表示树的大小与要求找到的路径的边权和。

接下来 \(n-1\) 行,每行三个整数 \(u_i,v_i,w_i\),代表有一条连接 \(u_i\) 与 \(v_i\),边权为 \(w_i\) 的无向边。

注意:点从 \(0\) 开始编号

输出格式

输出一个整数,表示最小边数量。

如果不存在这样的路径,输出 \(-1\)。

样例 #1

样例输入 #1

4 3
0 1 1
1 2 2
1 3 4

样例输出 #1

2

提示

对于 \(100\%\) 的数据,保证 \(1\leq n\leq 2\times10^5\),\(0\leq k,w_i\leq 10^6\),\(0\leq u_i,v_i<n\)。

codes

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
const int INF=1e6+100;
struct edge
{
    int y,n,z;
}e[N<<1];
int n,m,head[N],cnt;
int siz[N],root,all,mxa[N];
int qu[N],bi[N],uq[N],tot[INF],ed[N],ans=INF;
bool vis[N];
long long dis[N];
void ad(int x,int y,int z)
{
    e[++cnt].n=head[x];
    e[cnt].y=y;
    e[cnt].z=z;
    head[x]=cnt;
}

void getrt(int u,int fa)
{
    siz[u]=1;mxa[u]=0;
    for(int i=head[u];i;i=e[i].n)
    {
        int v=e[i].y;
        if(v==fa || vis[v])continue;
        getrt(v,u);
        siz[u]+=siz[v];
        mxa[u]=max(mxa[u],siz[v]);
    }
    mxa[u]=max(all-siz[u],mxa[u]);
    if(mxa[u]<mxa[root])root=u;
}

void getdis(int u,int fa,int d)
{
    if(dis[u]<=m)
    {
        qu[++qu[0]]=dis[u];
        bi[qu[0]]=d;
    }
    for(int i=head[u];i;i=e[i].n)
    {
        int v=e[i].y;
        if(v==fa || vis[v])continue;
        dis[v]=dis[u]+e[i].z;
        getdis(v,u,d+1);
    }

}

void calc(int u)
{
    int num=0;
    for(int i=head[u];i;i=e[i].n)
    {
        int v=e[i].y;
        if(vis[v])continue;

        qu[0]=0;
        dis[v]=e[i].z;
        getdis(v,0,1);

        for(int j=1;j<=qu[0];++j)
            if(qu[j]<=m)
            ans=min(tot[m-qu[j]]+bi[j],ans);
        for(int j=1;j<=qu[0];++j)
        {
            ++num;
            uq[num]=qu[j];
            tot[qu[j]]=min(tot[qu[j]],bi[j]);
        }
    }
    for(int i=1;i<=num;++i)
        tot[uq[i]]=INF;
}

void solve(int nw)
{
    vis[nw]=1;
    calc(nw);
    for(int i=head[nw];i;i=e[i].n)
    {
        int v=e[i].y;
        if(vis[v])continue;
        root=0;
        mxa[root]=INF;
        all=siz[v];
        getrt(v,0);
        solve(root);
    }
}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,z;i<n;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        ++x;++y;
        ad(x,y,z);ad(y,x,z);
    }
    for(int i=1;i<=m;++i)
        tot[i]=INF;
}

void work()
{
    all=n;
    mxa[root]=INF;
    getrt(1,0);
    solve(root);
    if(ans==INF)cout<<-1;
    else cout<<ans;
}
int main()
{
    init();
    work();
    return 0;
}

标签:int,IOI2011,样例,leq,Race,P4149,100
From: https://www.cnblogs.com/Glowingfire/p/18528964

相关文章

  • Array and string offset access syntax with curly braces is deprecated
    你遇到的这个问题确实是因为PHP版本升级后对一些语法的支持发生了变化。具体来说,从PHP7.4开始,使用大括号 {} 访问数组和字符串的偏移已经被弃用,并将在未来的版本中完全移除。因此,你需要对代码进行相应的调整。解决方法方法一:降级PHP版本更改PHP版本为7.0以下的版本:如果你......
  • 使用 ​​ltrace​​ 进行 Linux 库函数调用跟踪分析
    ltrace是Linux系统中的一个调试工具,主要用于跟踪应用程序调用的库函数。通过ltrace,可以查看应用程序在运行时调用了哪些共享库中的函数及其参数。这对于调试应用程序的行为,分析软件性能瓶颈,或理解某些程序与库的交互细节非常有用。以下是对ltrace的具体功能、用法和示例的详......
  • Spring中使用MDC和traceId实现日志链路追踪
    前言在系统出现问题时,我们常需要对日志进行分析,而如果日志打印时没有明确的标识,且日志内容不同线程很多时,很难找出哪段日志是我们需要的。针对这一问题,我们可以考虑使用MDC来实现日志链路追踪,迅速找到所需要的日志信息。当然,这也十分适合当下流行的微服务,特别是上下游节点有多个......
  • 【动态绘图】python 动态柱形图 动态折线图 bar_chart_race sjvisualizer
    本文主要介绍如何使用Python的bar_chart_race和sjvisualizer模块绘制动态柱形图和动态折线图。关于sjvisualizer包使用详细可见【动态绘图】上。一、实验环境1.1操作系统及Python环境本实验的所使用的操作系统为Windows1064位,Python版本为Python3.12.4,Python编译器......
  • 查看执行计划 autotrace 指标详解
    autotrace看执行计划,逻辑读,递归调用等sql执行信息。评估的执行计划非真实执行计划,即使是执行了,显示的均是explain的信息。执行输出示例:SQL>settimingonSQL>setautotraceonSQL>selectMGR,wm_concat(ENAME)fromemp2groupbyMGR;MGRWM_CONCAT(ENAME......
  • Android Framework: 增加trace点
    参考systrace/perfetto中需要actrace打tag相关方法-车载车机framework系统开发实战示例:+#defineATRACE_TAGATRACE_TAG_ALWAYS+#include<dlfcn.h>#include<iostream>+#include<utils/Trace.h>@@-55,6+58,7@@voidLogdStub::initLogLevel(){}boolLogd......
  • Race Track Generator Ultimate:Race Track Generator(赛车场赛道看台场景创建工具)
    下载:​​Unity资源商店链接资源下载链接效果图:......
  • Spring Cloud Gateway关键点全局Token过滤器,局部过滤器接口耗时,全链路跟踪TraceId日志
    一.全局Token过滤器在SpringCloudGateway中,实现全局过滤器的目的是对所有进入系统的请求或响应进行统一处理,比如添加日志、鉴权等。下面是如何创建一个全局过滤器的基本步骤:步骤1:创建过滤器类首先,你需要创建一个实现了GlobalFilter接口,创建一个全局token过滤器。@Slf......
  • 动态折线图bar_chart_race参数使用
    bar_chart_race主要参数与使用bar_chart_race包主要有两种主要函数(绘图,数据准备)。这里只用到bar_chart_race这一个函数,line_chart_race恕笔者是个笨比没跑通,prepare_wide_data和prepare_long_data可将pandasDataFrames转换为正确的形式,具体参见bar_chart_race数据准备。......