目录
题目链接题解代码
题目链接
bzoj 3991: [SDOI2015]寻宝游戏
题解
发现每次答案就是把虚树上的路径*2 接在同一关键点上的点的dfs序是相邻的 那么用set动态维护dfs序列 每次删点加点就好了
代码
#include<set>
#include<cstdio>
#include<algorithm>
#define gc getchar()
#define pc putchar
#define LL long long
inline int read() {
int x = 0,f = 1;
char c = gc;
while(c < '0' || c > '9') c = gc;
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;
return x * f;
}
void print(LL x) {
if(x < 0) {
pc('-');
x = -x;
}
if(x >= 10) print(x / 10);
pc(x % 10 + '0');
}
const int maxn = 100007;
int n,m;
struct node {
int v,next,w;
} edge[maxn << 1];
int head[maxn],num = 0;
inline void add_edge(int u,int v,int w) {
edge[++ num].v = v; edge[num].w = w; edge[num].next = head[u];head[u] = num;
}
std::set<int>s;
std::set<int> :: iterator it,qi,ho;
int deep[maxn],top[maxn],fa[maxn],son[maxn],siz[maxn];
LL dis[maxn];
void dfs1(int x,int f) {
deep[x] = deep[f] + 1,fa[x] = f;
siz[x] = 1;
for(int i = head[x];i;i = edge[i].next) {
int v = edge[i].v;
if(v != f) {
dis[v] = dis[x] + edge[i].w;
dfs1(v,x);
if(siz[v] > siz[son[x]]) son[x] = v;
siz[x] += siz[v];
}
}
}
int cnt = 0,dfn[maxn],ra[maxn];
void dfs2(int x,int tp) {
top[x] = tp; dfn[x] = ++ cnt;ra[cnt] = x;
if(son[x]) dfs2(son[x],tp);
for(int i = head[x];i;i = edge[i].next) {
int v = edge[i].v;
if(v == fa[x] || v == son[x]) continue;
dfs2(v,v);
}
}
int lca(int x,int y) {
while(top[x] != top[y]) {
if(deep[top[x]] > deep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
return deep[x] > deep[y] ? y : x;
}
LL query(int x) {
it = s.find(dfn[x]);
if(it == s.begin()) {qi = s.end();qi --; }
else {qi = it ;qi --; }
ho = it;ho ++;
if(ho == s.end()) ho = s.begin();
return dis[ra[* ho]] + dis[ra[* it]] * 2 + dis[ra[* qi]] - dis[lca(ra[* ho],ra[* it])] * 2 - dis[lca(ra[* it],ra[* qi])] * 2;
}
bool vis[maxn];
LL work(int x) {
it = s.find(dfn[x]);
if(it == s.begin()) {qi = s.end();qi --; }
else {qi = it; qi --;}
ho = it;ho ++;
if(ho == s.end()) ho = s.begin();
return dis[ra[*ho]] + dis[ra[*qi]] - 2 * dis[lca(ra[*qi],ra[*ho])];
}
int main() {
n = read(),m = read();
for(int u,v,w,i = 1;i < n;++ i) {
u = read(),v = read(),w = read();
add_edge(u,v,w); add_edge(v,u,w);
}
LL ans = 0;
dfs1(1,0);
dfs2(1,1);
for(int i = 1;i <= m;++ i) {
int x = read();
if(vis[x]) {
ans -= query(x);
ans += work(x);
s.erase(dfn[x]),vis[x] = 0;
} else {
vis[x] = 1;
s.insert(dfn[x]);
ans -= work(x);
ans += query(x);
}
printf("%lld\n",ans);
}
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/9715523.html
