LP3320 [SDOI2015]寻宝游戏

Author Avatar
空気浮遊 2018年06月09日
  • 在其它设备中阅读本文章
  • STL
  • lca
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

假虚树,真乱搞...

Problem

https://www.luogu.org/problemnew/solution/P3320

Solution

https://www.luogu.org/blog/zhouyuheng2003/solution-p3320

显然虚树并没有好写的动态维护方式
于是开个 set 大暴力就行

然后可以先算动态相邻再结算两头
这样子的话就不用管去掉两头的情况了
编程复杂度会低一些。

Code

// Code by ajcxsu
// Problem: tresuregame

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void gn(int &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=1e5+10, M=2e5+10;
int h[N], nexp[M], to[M], p=1;
ll W[M];
inline void ins(int a, int b, ll w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }

int n,m;
const int OP=21;
int dfn[N], dep[N], idx;
int gup[N][OP];
int nd[N];
ll sum[N][OP];
void dfs(int x, int k) {
    dep[x]=k, dfn[x]=++idx;
    nd[idx]=x;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            gup[to[u]][0]=x, sum[to[u]][0]=W[u];
            dfs(to[u], k+1);
        }
}
void ini() {
    dfs(1,1);
    for(int j=1;j<OP;j++)
    for(int i=1;i<=n;i++)
        gup[i][j]=gup[gup[i][j-1]][j-1], sum[i][j]=sum[i][j-1]+sum[gup[i][j-1]][j-1];
}

ll dis(int s, int t) {
    s=nd[s], t=nd[t];
    if(dep[s]<dep[t]) swap(s,t);
    ll ret=0;
    for(int j=OP-1;j>=0;j--)
        if(dep[gup[s][j]]>=dep[t]) ret+=sum[s][j], s=gup[s][j];
    if(s!=t) {
        for(int j=OP-1;j>=0;j--)
            if(gup[s][j]!=gup[t][j]) ret+=sum[s][j]+sum[t][j], s=gup[s][j], t=gup[t][j];
        ret+=sum[s][0]+sum[t][0];
    }
    return ret;
}

set<int> nset;
bool li[N];

int main() {
    gn(n), gn(m);
    int u,v,w;
    for(int i=0;i<n-1;i++) gn(u), gn(v), gn(w), ins(u,v,w), ins(v,u,w);
    ini();
    nset.insert(0), nset.insert(n+1);
    int na;
    ll ans=0;
    while(m--) {
        gn(na);
        ll d=-1,ext;
        if(!li[na]) d=1, nset.insert(dfn[na]), li[na]=1;
        else if(li[na]) li[na]=0;
        int bef=*(--nset.find(dfn[na])), aft=*(++nset.find(dfn[na]));
        if(bef>=1) ans+=d*dis(bef, dfn[na]);
        if(aft<=n) ans+=d*dis(dfn[na], aft);
        if(bef>=1 && aft<=n) ans-=d*dis(bef, aft);
        if(!li[na]) nset.erase(dfn[na]);
        bef=*++nset.find(0);
        aft=*--nset.find(n+1);
        if(bef<aft) ext=dis(bef, aft);
        else ext=0;
        printf("%lld\n", ans+ext);
    }
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-luogu-3320.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material