P6869 Putovanje

P6869 Putovanje

P6869 Putovanje - 洛谷

题意：

n 个节点的树

按照编号从小到大访问每个节点

每次经过树边时需要收费，可购买单程票\(c_1\)，或者多程票\(c_2\)供无限次使用

求最小费用

思路：

用几个例子观察 "按照编号从小到大访问每个节点"

先不看费用，只看这几个例子，经过的边有什么规律：

比如：

一条边被经过了几次？

总共遍历了多少条边？（重复遍历也要计数）

e.g. 一开始想到了...

从1开始访问

每到一个节点 i

若这个节点为根的树

1. 满足儿子均大于它，那么只需要走 \((size[i]-1) \times 2 -1\)步

   (如果是还要回到根节点的话， \((size[i]-1) \times 2\)

2. 满足儿子均小于它，那么一定需要走 \((size[i]-1) \times 2\) 步，回到该节点

3. 有的儿子小于它，有的儿子大于它 ... ...

观察 图1，图3

图1：\(3→4\)，经过的路径恰好是 ?

\(3→lca(3,4)→4\)

图3：\(2→3\) 经过的路径是 ？

\(2→lca(2,3)→3\)

更一般地，观察图3：

• \(1→2\) 经过的路径
• \(5→6\) 经过的路径

---

思考 按照编号从小到大访问每个节点，实际上是怎么遍历边的？

---

总结：

按顺序遍历 \(1-n\)，求出\(LCA(i,i+1)\)

让\(i → LCA(i,i+1) → i+1\)上的每条边计数+1

最后，遍历每条边，根据**计数x单程价 ?_ 多程价 **，决定答案

(1) 将树边信息下沉到对应的点上，方便求解

(2) \(i→i+1\)：经过的每条边都要计数+1

信息下沉到点之后，只需要用(dif数组)维护端点信息(i,i+1,lca(i,i+1))，最后做一次后序遍历的前缀和即可

(3) 固定 1 为根

下沉的时候，是有方向的

\(u→v\)：有一条直连边

若fa[u][0]=v，则边信息下传给u (或者depth[u]>depth[v])

---

代码:

const ll N=4e5+5;
const ll K=20;
ll depth[N],fa[N][21];
vector e[N];

struct edge{ll s,e,c1,c2;};
vector ed; //保存边信息

struct node{ll c1,c2;};
vector nd;
vector dif;

void dfs1(ll x,ll f)
{
    fa[x][0]=f; depth[x]=depth[f]+1;
    for(ll i=1;i<=K;++i){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }

    //cerr<=0;--i){
        if(depth[fa[x][i]]>=depth[y])
            x=fa[x][i];
    }
    if(x==y) return x;

    for(ll i=K;i>=0;--i){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}

void dfs2(ll x,ll f) //前缀和
{
    for(ll v:e[x]){
        if(v==f) continue;
        dfs2(v,x);
    }
    for(ll v:e[x]){
        if(v!=f) dif[x]+=dif[v];
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    ll n,a,b,c1,c2;
    cin>>n;
    nd.resize(n+1);
    for(ll i=1;i>a>>b>>c1>>c2;
        e[a].push_back(b);
        e[b].push_back(a);
        ed.push_back({a,b,c1,c2}); //存边
    }
    dfs1(1,0);
    for(auto& [a,b,c1,c2]:ed){ //下沉信息
        if(fa[a][0]==b) swap(a,b);//默认a=fa[b][0],如果不是swap
        nd[b]={c1,c2};
    }

    dif.resize(n+1,0);
    for(ll i=1;ind[i].c2){//乘法记得ll
            ans+=nd[i].c2;
        }else{
            ans+=dif[i]*nd[i].c1;
        }
    }
    cout<

"