其實(shí)我做這題為時(shí)尚早

做這題之前先學(xué)習(xí)set

#include<bits/stdc++.h> #define MN 200050 #define ll long long using namespace std; set<ll>s; set<ll>::iterator it; ll n,m,cnt,head[MN],dfn[MN],dep[MN],num[MN]; ll vis[MN]; ll f[MN][21]; ll lg[MN]; ll dis[MN][18]; ll idx; ll Ans; struct tu {ll v,nxt;ll w; } e[MN]; void add(ll u,ll v,ll w) {e[++cnt].v=v;e[cnt].nxt=head[u];e[cnt].w=w;head[u]=cnt; } void dfs(ll now,ll fa) {dep[now]=dep[fa]+1;dfn[now]=++idx;f[now][0]=fa;num[idx]=now;for(ll i=1; i<=lg[dep[now]]; i++){f[now][i]=f[f[now][i-1]][i-1];dis[now][i]=dis[now][i-1]+dis[f[now][i-1]][i-1];}for(ll i=head[now]; i; i=e[i].nxt){ll v=e[i].v;if(v!=fa){dis[e[i].v][0]=e[i].w;dfs(v,now);}} } ll getl(ll x) {it=s.lower_bound(x);if(it==s.begin())it=s.end();return *--it; } ll getr(ll x) {it=s.lower_bound(x);if(++it==s.end())it=s.begin();return *it; } ll lca(ll x,ll y) {if(dep[x]<dep[y])swap(x,y);ll ans=0;while(dep[x]!=dep[y]){ans+=dis[x][lg[dep[x]-dep[y]]];x=f[x][lg[dep[x]-dep[y]]];}if(x==y)return ans;for(ll k=lg[dep[x]]; k>=0; k--) {if(f[x][k]==f[y][k])continue;ans+=dis[x][k]+dis[y][k],x=f[x][k],y=f[y][k]; } return ans+dis[x][0]+dis[y][0]; }int main() {scanf("%lld%lld\n",&n,&m);lg[0]=-1;ll sum=0;for(ll i=1; i<=n; i++)lg[i]=lg[i/2]+1;for(ll i=1; i<=n-1; i++){ll x,y,z;scanf("%lld%lld%lld",&x,&y,&z);add(x,y,z);add(y,x,z);}dfs(1,0);ll x;for(ll i=1; i<=m; i++){scanf("%lld",&x);if (!vis[x]){vis[x]^=1;s.insert(dfn[x]);sum+=lca(num[getl(dfn[x])],x)+lca(num[getr(dfn[x])],x)-lca(num[getl(dfn[x])],num[getr(dfn[x])]);}else{vis[x]^=1;sum-=lca(num[getl(dfn[x])],x)+lca(num[getr(dfn[x])],x)-lca(num[getl(dfn[x])],num[getr(dfn[x])]); s.erase(dfn[x]);}printf("%lld\n",sum);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zw130-lzr-blogs/p/10971385.html

總結(jié)

以上是生活随笔為你收集整理的SDOI2015寻宝游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。