题解

2 条题解

  • 2
    @ 2017-05-27 21:58:07

    惨啊,一开始打了个虚树模板,后来才发现居然是dfs+set
    幸好树剖求LCA没有白写QWQ

    #include<stdio.h>
    #include<string.h>
    #include<set>
    #include<algorithm>
    #define N 100010
    typedef long long L;
    using namespace std;
    struct E{ int v,c,nt; } G[N<<1]; set<int> s;
    int f[N],sz[N],son[N],h[N]={0},d[N]={0},t[N]={0};
    int dfn[N],cnt=0,d_cl=0,n,m,r[N];
    L dis[N],ans=0ll; bool v[N]={0};
    inline void adj(int a,int b,int c){
        G[++cnt]=(E){b,c,h[a]}; h[a]=cnt;
        G[++cnt]=(E){a,c,h[b]}; h[b]=cnt;
    }
    void dijk(int x,int p){
        f[x]=p; d[x]=d[p]+1; son[x]=0; sz[x]=1;
        for(int v,i=h[x];i;i=G[i].nt){
            if((v=G[i].v)==p) continue;
            dis[v]=dis[x]+G[i].c; dijk(v,x);
            sz[x]+=sz[v];
            if(sz[v]>sz[son[x]]) son[x]=v;
        }
    }
    void spfa(int x,int p){
        t[x]=p; r[dfn[x]=++d_cl]=x;
        if(son[x]) spfa(son[x],p);
        for(int v,i=h[x];i;i=G[i].nt)
            if((v=G[i].v)!=f[x]&&v!=son[x]) spfa(v,v);
    }
    int dx(int x,int y){
        while(t[x]!=t[y]) 
            if(d[t[x]]>d[t[y]]) x=f[t[x]];else y=f[t[y]];
        return d[x]<d[y]?x:y;
    }
    long long dist(int x,int y){
        return dis[x]+dis[y]-2*dis[dx(x,y)];
    }
    void in(int x){
        s.insert(dfn[x]);
        set<int>::iterator it;
        it=s.find(dfn[x]); 
        int a=(it==s.begin()?0:r[*--it]);
        it=s.find(dfn[x]); 
        int b=(++it==s.end()?0:r[*it]);
        if(a) ans+=dist(a,x);
        if(b) ans+=dist(x,b);
        if(a&&b) ans-=dist(a,b);
    }
    void del(int x){
        set<int>::iterator it;
        it=s.find(dfn[x]); 
        int a=(it==s.begin()?0:r[*--it]);
        it=s.find(dfn[x]); 
        int b=(++it==s.end()?0:r[*it]);
        if(a) ans-=dist(a,x);
        if(b) ans-=dist(x,b);
        if(a&&b) ans+=dist(a,b);
        s.erase(dfn[x]);
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int a,b,c,i=1;i<n;++i) 
            scanf("%d%d%d",&a,&b,&c),adj(a,b,c);
        dijk(1,0); spfa(1,1);
        for(int x,i=0;i<m;++i){
            scanf("%d",&x);
            if(v[x]) del(x); else in(x); v[x]^=1;
            printf("%lld\n",s.size()?ans+dist(r[*s.begin()],r[*--s.end()]):0);
        }
    }
    
  • 0
    @ 2020-04-30 17:05:53

    用 STL 自带的 set 容器维护起来很方便。你也可以手写树状数组/线段树/平衡树。

    #include <cstdio>
    #include <set>

    typedef long long LL;
    const int MN = 100005;

    int N, M;
    int h[MN], nxt[MN * 2], to[MN * 2], w[MN * 2], tot;
    inline void ins(int x, int y, int z) {
    nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot;
    }

    int dfn[MN], idf[MN], dfc;
    int dep[MN], faz[MN][17];
    LL dis[MN];

    void DFS(int u, int fz) {
    dfn[u] = ++dfc; idf[dfc] = u; dep[u] = dep[faz[u][0] = fz] + 1;
    for (int j = 1; 1 << j < dep[u]; ++j) faz[u][j] = faz[faz[u][j - 1]][j - 1];
    for (int i = h[u]; i; i = nxt[i]) if (to[i] != fz) dis[to[i]] = dis[u] + w[i], DFS(to[i], u);
    }

    inline int lca(int x, int y) {
    if (dep[x] < dep[y]) std::swap(x, y);
    for (int d = dep[x] - dep[y], j = 0; d; d >>= 1, ++j)
    if (d & 1) x = faz[x][j];
    if (x == y) return x;
    for (int j = 16; ~j; --j) if (faz[x][j] != faz[y][j])
    x = faz[x][j], y = faz[y][j];
    return faz[x][0];
    }

    inline LL dist(int x, int y) { return dis[x] + dis[y] - 2 * dis[lca(x, y)]; }

    bool vis[MN];
    std::set<int> st;
    std::set<int>::iterator it;
    LL Ans;

    int main() {
    scanf("%d%d", &N, &M);
    for (int i = 1, x, y, z; i < N; ++i) {
    scanf("%d%d%d", &x, &y, &z);
    ins(x, y, z), ins(y, x, z);
    }
    DFS(1, 0);
    for (int m = 1, x, y, z; m <= M; ++m) {
    scanf("%d", &x);
    x = dfn[x];
    if (!vis[idf[x]]) st.insert(x);
    y = idf[(it = st.lower_bound(x)) == st.begin() ? *--st.end() : *--it];
    z = idf[(it = st.upper_bound(x)) == st.end() ? *st.begin() : *it];
    if (vis[idf[x]]) st.erase(x);
    x = idf[x];
    LL d = dist(x, y) + dist(x, z) - dist(y, z);
    if (!vis[x]) vis[x] = 1, Ans += d;
    else vis[x] = 0, Ans -= d;
    printf("%lld\n", Ans);
    }
    return 0;
    }

  • 1

信息

ID
1946
难度
6
分类
(无)
标签
递交数
79
已通过
22
通过率
28%
被复制
2
上传者