acwing264作诗 [操作系统入门]

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

点分冶是一种在树上处理区间问题的一种方式，对于一个树上两点之间的的路径，如果我们设置一个指定节点p(为树的重心)为根节点，那么会存在两种情况:

  1. 路径经过了根节点p

  2. 路径包含于p的某一棵子树中  

对于第二类我们可以递归进行处理，对于第一类，我们将路径分为"x~p"和"p~y"两段，从p开始进行dfs,求出数组d和数组b，d[x]表示x到p的距离，b[x]表示属于哪一棵子树。

一般点分冶的过程是：

  1. 通过dfs求树的重心p

  2. 从p开始dfs，求出两个数组

  3. 执行计算

  4. 对p子树进行递归计算

#include<bits/stdc++.h>
usingnamespace std;
const ll INF=1ll<<58;
/**********/
#define MAXN 200011
#define MAXK 1000011
struct edge
{
    ll v,w,nxt;
}e[MAXN<<1|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
++cnt;
    e[cnt].v=v,e[cnt].w=w;
    e[cnt].nxt=last[u],last[u]=cnt;
}
bool vis[MAXN];
ll size[MAXN];
void dfs1(ll u,ll fa)
{
    size[u]=1;
for(ll i=last[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
if(vis[v]||v==fa)continue;
        dfs1(v,u);
        size[u]+=size[v];
    }
}
ll dfs2(ll u,ll all,ll fa)
{
    ll mson=0;
for(ll i=last[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
if(vis[v]||v==fa)continue;
if(size[v]>size[mson])mson=v;
    }
if(size[mson]>all/2)return dfs2(mson,all,u);
return u;
}
std::vector<ll>a[MAXN];
ll sum[MAXN],len[MAXN];
void dfs3(ll u,ll fa,ll rt)
{
    a[rt].push_back(u);
for(ll i=last[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
if(vis[v]||v==fa)continue;
        sum[v]=sum[u]+e[i].w;
        len[v]=len[u]+1;
        dfs3(v,u,rt);
    }
}
ll ans=INF,f[MAXK],n,k;
void solve(ll u)
{
    dfs1(u,0);
    u=dfs2(u,size[u],0);
//printf("visit %lld
",u);
    vis[u]=1,sum[u]=len[u]=0;
    ll cnt=0;
    a[++cnt].push_back(u);
for(ll i=last[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
if(!vis[v])sum[v]=e[i].w,len[v]=1,dfs3(v,u,++cnt);
    }
for(ll i=1;i<=cnt;++i)
    {
for(ll j=0;j<a[i].size();++j)
        {
            ll v=a[i][j];
if(sum[v]<=k)umin(ans,f[k-sum[v]]+len[v]);
        }
for(ll j=0;j<a[i].size();++j)
        {
            ll v=a[i][j];
if(sum[v]<=k)umin(f[sum[v]],len[v]);
        }
    }
for(ll i=1;i<=cnt;a[i].clear(), ++i)
for(ll j=0;j<a[i].size();++j)
        {
            ll v=a[i][j];
if(sum[v]<=k)f[sum[v]]=INF;
        }
//
for(ll i=last[u];i;i=e[i].nxt)
if(!vis[e[i].v])solve(e[i].v);
}
int main()
{
    n=read(),k=read();
for(ll i=1;i<n;++i)
    {
        ll u=read()+1,v=read()+1,w=read();
        adde(u,v,w),adde(v,u,w);
    }
    memset(f,0x3f,sizeof f);
    solve(1);
    printf("%lld",ans<=n?ans:-1ll);
return0;
}

 

acwing 264 作诗

以上是 acwing264作诗 [操作系统入门] 的全部内容， 来源链接： utcz.com/z/519137.html

回到顶部