题解 P6869 【[COCI2019-2020#5] Putovanje】

· · 题解

原题传送门

前置知识：

  1. P3379 【模板】最近公共祖先（LCA）
  2. 树上差分——P3128 [USACO15DEC]Max Flow P

考虑这样一个性质：如果你第一次走过一条边买了多程票，就不会再买这条边的单程票。反之亦然。

所以对于每一条边，我们一定只买单程票或多程票。

于是只要求出每条边经过的次数 k ，然后算出你需要花在这条边上的最少花费 \min(k\times c_{i1},c_{i2}) 统计进答案。

每条边经过的次数用树上差分搞，由于是边差分，直接在 val_{\operatorname{lca(u,v)}} 上减两次。

Code

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N=2e5+10;

int n,fir[N],tot,fa[N][40],dep[N];
long long ans,val[N];
struct node {int to,nex,oned,twod;} e[N << 1];

void add(int u,int v,int xgf,int xrc)
{
    e[++tot].to=v;
    e[tot].oned=xgf;//这是两位同级机房神仙的名字
    e[tot].twod=xrc;
    e[tot].nex=fir[u];
    fir[u]=tot;
    return ;
}
void swap(int &x,int &y) {x^=y^=x^=y; return ;}

void dfs(int x,int dad)//LCA预处理
{
    dep[x]=dep[dad]+1;
    fa[x][0]=dad;
    for(int i=1;(1<<i)<=dep[x];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=fir[x];i;i=e[i].nex)
        if(e[i].to^dad) dfs(e[i].to,x);
    return ;
}

int lca(int x,int y)//倍增求LCA
{
    if(dep[x] < dep[y]) swap(x,y);
    for(int i=35;i>=0;i--)
    {
        if(dep[fa[x][i]] >= dep[y]) x=fa[x][i];
        if(x == y) return y;
    }
    for(int i=35;i>=0;i--)
        if(fa[x][i]^fa[y][i]) {x=fa[x][i]; y=fa[y][i];}
    return fa[x][0];
}

void solve(int x)
{
    int u;
    for(int i=fir[x];i;i=e[i].nex)
        if(e[i].to^fa[x][0])
        {
            solve(e[i].to);
            val[x]+=val[e[i].to];//统计经过的次数
        }
        else u=i;
    if(e[u].oned*val[x] < e[u].twod) ans+=e[u].oned*val[x];
    else ans+=e[u].twod;//统计答案
    return ;
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d",&n);
    for(int i=1,u,v,c1,c2;i<n;i++)
    {
        scanf("%d%d%d%d",&u,&v,&c1,&c2);
        add(u,v,c1,c2); add(v,u,c1,c2);
    }
    dfs(1,0);
    for(int i=1;i<n;i++)
    {
        val[i]++; val[i+1]++;
        val[lca(i,i+1)]-=2;//树上差分，题目要求编号从小到大访问
    }
    solve(1);
    printf("%lld",ans);
//  fclose(stdin); fclose(stdout);
    return 0;
}

感谢阅读！您的点赞和留言是对作者最大的支持！