loj2182 「SDOI2015」寻宝游戏
参考这里
#include
#include
#include
using namespace std;
typedef long long ll;
int n, m, ise[100005], fa[100005][19], dep[100005], uu, vv, ww, hea[100005], cnt;
int faq, nfd[100005];
ll dis[100005], ans;
struct Edge{int too, nxt, val;
}edge[200005];
struct Node{int idx, dfn;bool operator<(const Node &x)const{return dfn qwq;
void add_edge(int fro, int too, int val){edge[++cnt].nxt = hea[fro];edge[cnt].too = too;edge[cnt].val = val;hea[fro] = cnt;
}
void dfs(int x, int f, ll d){nfd[x] = ++faq;dis[x] = d;fa[x][0] = f;dep[x] = dep[f] + 1;for(int i=hea[x]; i; i=edge[i].nxt){int t=edge[i].too;if(t!=f) dfs(t, x, d+edge[i].val);}
}
int queryPre(int x){set::iterator i=qwq.lower_bound((Node){x, nfd[x]});if(i==qwq.begin()) i = qwq.end();return (*(--i)).idx;
}
int queryNxt(int x){set::iterator i=qwq.lower_bound((Node){x, nfd[x]});if((++i)==qwq.end()) i = qwq.begin();return (*i).idx;
}
int lca(int x, int y){if(dep[x]=0; i--)if(dep[fa[x][i]]>=dep[y])x = fa[x][i];if(x==y) return x;for(int i=16; i>=0; i--)if(fa[x][i]!=fa[y][i]){x = fa[x][i];y = fa[y][i];}return fa[x][0];
}
ll qdis(int x, int y){return dis[x]+dis[y]-2*dis[lca(x, y)];
}
ll query(int x){int pre, nxt, fla;if(!ise[x]){fla = 1;qwq.insert((Node){x, nfd[x]});pre = queryPre(x);nxt = queryNxt(x);}else{fla = -1;pre = queryPre(x);nxt = queryNxt(x);qwq.erase((Node){x, nfd[x]});}ise[x] ^= 1;if(qwq.size()<=1) ans = 0;else ans += fla * (qdis(pre, x)+qdis(x, nxt)-qdis(pre, nxt));return ans;
}
int main(){cin>>n>>m;for(int i=1; i 转载于:https://www.cnblogs.com/poorpool/p/8746806.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！