BZOJ 3991: [SDOI2015]寻宝游戏

正文索引 [隐藏]

题解
代码

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3991

题解

求一棵树上若干个关键点的最短路
就是求虚树上相邻的两个点的距离之和
用set维护DFS虚，然后LCA维护距离

代码

//while(true) RP++;
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#define LL long long
using namespace std;
const int Maxn=100000;
const int Maxd=20;
struct Edge{
    int v,nxt;
    LL dis;
    Edge(){}
    Edge(int v0,int n0,LL d0){
        v=v0;
        nxt=n0;
        dis=d0;
    }
};
Edge e[Maxn*2+5];
int head[Maxn+5];
int nume;
inline void addEdge(int u,int v,LL dis){
    e[++nume]=Edge(v,head[u],dis);
    head[u]=nume;
    e[++nume]=Edge(u,head[v],dis);
    head[v]=nume;
}
int fa[Maxn+5][25];
int dfn[Maxn+5],dep[Maxn+5];
LL dis[Maxn+5];
int tim;
void dfs(int x){
    dfn[x]=++tim;
    for (int i=1;i<=Maxd;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v;
        if (dfn[v]) continue;
        fa[v][0]=x;
        dep[v]=dep[x]+1;
        dis[v]=dis[x]+e[i].dis;
        dfs(v);
    }
}
inline void swim(int &x,int t){
    for (int i=0;t;t/=2,i++) if (t&1) x=fa[x][i];
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    swim(x,dep[x]-dep[y]);
    if (x==y) return x;
    for (int i=Maxd;i>=0;i--){
        if (fa[x][i]==fa[y][i]) continue;
        x=fa[x][i];
        y=fa[y][i];
    }
    return fa[x][0];
}
struct Node{
    int dfn;
    int index;
    bool operator <(Node const b)const{
        return dfn<b.dfn;
    }
    bool operator ==(Node const b)const{
        if (dfn==b.dfn) return true;
    }
    bool operator >(Node const b)const{
        return dfn>b.dfn;
    }
    Node(){}
    Node(int d0,int i0){
        dfn=d0;
        index=i0;
    }
};
set<Node> tree;
int n,m;
LL Ans;
bool goods[Maxn+5];
inline set<Node>::iterator getPrev(set<Node>::iterator it){
    set<Node>::iterator tmp=it;
    if (tmp==tree.begin()) tmp=tree.end();
    tmp--;
    return tmp;
}
inline set<Node>::iterator getNext(set<Node>::iterator it){
    set<Node>::iterator tmp=it;
    tmp++;
    if (tmp==tree.end()) tmp=tree.begin();
    return tmp;
}
inline LL getDist(int x,int y){
    int lca=LCA(x,y);
    //printf("GetDist %d %d %lld\n",x,y,dis[x]+dis[y]-dis[lca]*2LL);
    return dis[x]+dis[y]-dis[lca]*2LL;
}
inline void ins(int x){
    set<Node>::iterator it=tree.insert(Node(dfn[x],x)).first;
    int prev=(*getPrev(it)).index,nxt=(*getNext(it)).index;
    if (tree.size()<=1){
        Ans=0;
    }else{
        Ans-=getDist(prev,nxt);
        Ans+=getDist(prev,x)+getDist(x,nxt);
    }
}
inline void del(int x){
    set<Node>::iterator it=tree.find(Node(dfn[x],x));
    int prev=(*getPrev(it)).index,nxt=(*getNext(it)).index;
    tree.erase(Node(dfn[x],x));
    if (tree.size()<=1){
        Ans=0;
    }else{
        Ans-=getDist(prev,x)+getDist(x,nxt);
        Ans+=getDist(prev,nxt);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++){
        int x,y;
        LL d;
        scanf("%d%d%lld",&x,&y,&d);
        addEdge(x,y,d);
    }
    fa[1][0]=1;
    dep[1]=1;
    dis[1]=0;
    dfs(1);
    tree.clear();
    Ans=0;
    for (int i=1;i<=m;i++){
        int pos;
        scanf("%d",&pos);
        if (!goods[pos]) ins(pos); else del(pos);
        goods[pos]=!goods[pos];
        printf("%lld\n",Ans);
        //printf("%d\n",(*tree.end()).index);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

//while(true) RP++;

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<set>

#define LL long long

using namespace std;

const int Maxn=100000;

const int Maxd=20;

struct Edge{

int v,nxt;

LL dis;

Edge(){}

Edge(int v0,int n0,LL d0){

v=v0;

nxt=n0;

dis=d0;

}

};

Edge e[Maxn*2+5];

int head[Maxn+5];

int nume;

inline void addEdge(int u,int v,LL dis){

e[++nume]=Edge(v,head[u],dis);

head[u]=nume;

e[++nume]=Edge(u,head[v],dis);

head[v]=nume;

}

int fa[Maxn+5][25];

int dfn[Maxn+5],dep[Maxn+5];

LL dis[Maxn+5];

int tim;

void dfs(int x){

dfn[x]=++tim;

for (int i=1;i<=Maxd;i++)

fa[x][i]=fa[fa[x][i-1]][i-1];

for (int i=head[x];i;i=e[i].nxt){

int v=e[i].v;

if (dfn[v]) continue;

fa[v][0]=x;

dep[v]=dep[x]+1;

dis[v]=dis[x]+e[i].dis;

dfs(v);

}

inline void swim(int &x,int t){

for (int i=0;t;t/=2,i++) if (t&1) x=fa[x][i];

}

inline int LCA(int x,int y){

if (dep[x]<dep[y]) swap(x,y);

swim(x,dep[x]-dep[y]);

if (x==y) return x;

for (int i=Maxd;i>=0;i--){

if (fa[x][i]==fa[y][i]) continue;

x=fa[x][i];

y=fa[y][i];

}

return fa[x][0];

}

struct Node{

int dfn;

int index;

bool operator <(Node const b)const{

return dfn<b.dfn;

}

bool operator ==(Node const b)const{

if (dfn==b.dfn) return true;

}

bool operator >(Node const b)const{

return dfn>b.dfn;

}

Node(){}

Node(int d0,int i0){

dfn=d0;

index=i0;

}

};

set<Node> tree;

int n,m;

LL Ans;

bool goods[Maxn+5];

inline set<Node>::iterator getPrev(set<Node>::iterator it){

set<Node>::iterator tmp=it;

if (tmp==tree.begin()) tmp=tree.end();

tmp--;

return tmp;

}

inline set<Node>::iterator getNext(set<Node>::iterator it){

set<Node>::iterator tmp=it;

tmp++;

if (tmp==tree.end()) tmp=tree.begin();

return tmp;

}

inline LL getDist(int x,int y){

int lca=LCA(x,y);

//printf("GetDist %d %d %lld\n",x,y,dis[x]+dis[y]-dis[lca]*2LL);

return dis[x]+dis[y]-dis[lca]*2LL;

}

inline void ins(int x){

set<Node>::iterator it=tree.insert(Node(dfn[x],x)).first;

int prev=(*getPrev(it)).index,nxt=(*getNext(it)).index;

if (tree.size()<=1){

Ans=0;

}else{

Ans-=getDist(prev,nxt);

Ans+=getDist(prev,x)+getDist(x,nxt);

}

inline void del(int x){

set<Node>::iterator it=tree.find(Node(dfn[x],x));

int prev=(*getPrev(it)).index,nxt=(*getNext(it)).index;

tree.erase(Node(dfn[x],x));

if (tree.size()<=1){

Ans=0;

}else{

Ans-=getDist(prev,x)+getDist(x,nxt);

Ans+=getDist(prev,nxt);

}

int main(){

scanf("%d%d",&n,&m);

for (int i=1;i<n;i++){

int x,y;

LL d;

scanf("%d%d%lld",&x,&y,&d);

addEdge(x,y,d);

}

fa[1][0]=1;

dep[1]=1;

dis[1]=0;

dfs(1);

tree.clear();

Ans=0;

for (int i=1;i<=m;i++){

int pos;

scanf("%d",&pos);

if (!goods[pos]) ins(pos); else del(pos);

goods[pos]=!goods[pos];

printf("%lld\n",Ans);

//printf("%d\n",(*tree.end()).index);

}

return 0;

}

WNJXYKの博客

喂你脚下有坑

BZOJ 3991: [SDOI2015]寻宝游戏

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

2022年 8月
一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

BZOJ 3991: [SDOI2015]寻宝游戏

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗