算法
QAQ,其实我只是觉得我的码风好看才放上来的~
给同学们提供一波chao的板子~
emm update.10.30
异象石那道题的话你可以先考虑这样一个问题,给你一棵任意形态的树,那么如果你把他的dfs序排成一圈首尾相接,然后将相邻两点的路径长度相加,得到的答案刚好是答案的两倍,这种结论我就直接手膜+感性理解了,然后我们发现如果动态加或删点的话,我们只要用set维护一下dfn的相对大小,然后加减路径长度即可@
C++ 代码
QAQ,魔鬼输入格式呢~
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 500000
int head[maxn],nxt[maxn],to[maxn],val[maxn],vis[maxn];
int dfn[maxn],idf[maxn],dis[maxn],dep[maxn],fa[maxn][20];
int n,m,cnt,ans,tot;
std::set<int> st;
std::set<int>::iterator it;
void add(int u,int v,int w){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
val[cnt]=w;
}
void dfs(int u,int f){
fa[u][0]=f;
dep[u]=dep[f]+1;
dfn[u]=++tot;
idf[tot]=u;
for(int i=1;(1<<i)<dep[u];i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==fa[u][0]) continue;
dis[v]=dis[u]+val[i];
dfs(v,u);
}
}
int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int j=dep[x]-dep[y],i=0;j;j>>=1,i++){
if(j&1)x=fa[x][i];
}
if(x==y) return x;
for(int i=18;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];y=fa[y][i];
}
}
return fa[x][0];
}
int dist(int x,int y){
return dis[x]+dis[y]-2*dis[getlca(x,y)];
}
void update(int x){
x=dfn[x];
if(!vis[idf[x]]) st.insert(x);
int y=idf[(it=st.lower_bound(x))==st.begin() ? *--st.end():*--it];
int z=idf[(it=st.upper_bound(x))==st.end() ? *st.begin():*it];
if(vis[idf[x]]) st.erase(x);
x=idf[x];
int d=dist(x,y)+dist(x,z)-dist(y,z);
if(!vis[x]) vis[x]=1,ans+=d;
else vis[x]=0,ans-=d;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs(1,1);
scanf("%lld",&m);
for(int i=1;i<=m;i++){
int x;char c;
cin>>c;
if(c=='?')printf("%lld\n",ans/2);
else scanf("%lld",&x),update(x);
}
return 0;
}
%%%
太神了%%%