【BZOJ】3991 [SDOI2015]尋寶遊戲 樹形DP+虛樹+set

題目傳送門

其實這題并沒有真正的用到虛樹，隻是用到了虛樹的思想。

首先考慮暴力樹形DP，時間複雜度還是 O(n×m) ，必須要優化。

然後我們把思路轉移到虛樹上，發現問題轉化為改變一個節點是否為關鍵點，答案就是虛樹上所有邊權*2。

我們考慮一個節點加入虛樹産生的貢獻，就是DFS序中和目前節點相鄰的節點的路徑長度*2，删除同理。那麼我們每次維護改變的節點的貢獻即可。

可以用一個set來維護目前虛樹中的節點，然後就變成了求前驅後繼之類的操作。

注意：樹根不是1，但也不能每次減目前樹根的深度，是以我們放在最後讓樹鍊的并減去樹根的深度。

p.s.十年OI一場空，不開long long見祖宗……記得開long long啊……

附上AC代碼：

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <set>
using namespace std;

typedef long long ll;
const int N=+;
struct side{
    ll to,w,nt;
}s[N<<];
int n,m,h[N],num,a[N],t;
int d[N],f[N],sz[N],hs[N],top[N],wz[N],size,rl[N],x,y,w;
bool b[N];
set <int> u;
set <int> :: iterator it;
ll ans,tmp,dis[N];

inline char nc(void){
    static char ch[],*p1=ch,*p2=ch;
    return p1==p2&&(p2=(p1=ch)+fread(ch,,,stdin),p1==p2)?EOF:*p1++;
}

inline void read(int &a){
    static char c=nc();int f=;
    for (;!isdigit(c);c=nc()) if (c=='-') f=-;
    for (a=;isdigit(c);a=(a<<)+(a<<)+c-'0',c=nc());
    return (void)(a*=f);
}

inline void add(int x,int y,ll w){
    s[++num]=(side){y,w,h[x]},h[x]=num;
    s[++num]=(side){x,w,h[y]},h[y]=num;
}

inline void so1(int x,int fa){
    d[x]=d[f[x]=fa]+,sz[x]=;
    for (int i=h[x]; i; i=s[i].nt)
        if (s[i].to!=fa){
            dis[s[i].to]=dis[x]+s[i].w,so1(s[i].to,x),sz[x]+=sz[s[i].to];
            if (sz[s[i].to]>sz[hs[x]]) hs[x]=s[i].to;
        }
    return;
}

inline void so2(int x,int fa){
    top[x]=fa,wz[x]=++size,rl[size]=x;
    if (hs[x]) so2(hs[x],fa);
    for (int i=h[x]; i; i=s[i].nt)
        if (s[i].to!=f[x]&&s[i].to!=hs[x]) so2(s[i].to,s[i].to);
    return;
}

inline int lca(int x,int y){
    for (int fx=top[x],fy=top[y]; fx!=fy; x=f[fx],fx=top[x])
        if (d[fx]<d[fy]) swap(fx,fy),swap(x,y);
    return d[x]<d[y]?x:y;
}

inline ll calc(int x,int y){return dis[x]+dis[y]-(dis[lca(x,y)]<<);}

int main(void){
    read(n),read(m);
    for (int i=; i<n; ++i) read(x),read(y),read(w),add(x,y,l*w);
    so1(,),so2(,),u.insert(-),u.insert();
    while (m--){
        read(x);
        if (a[x]) u.erase(wz[x]),t=-;
        else u.insert(wz[x]),t=;
        a[x]^=,it=u.upper_bound(wz[x]);
        int r=*it,l=*(--it); if (l>=wz[x]) l=*(--it);
        if (l!=-) ans+=calc(rl[l],x)*t; if (r!=) ans+=calc(rl[r],x)*t;
        if (l!=-&&r!=) ans-=calc(rl[l],rl[r])*t;
        tmp=(u.size()>)?calc(rl[*u.upper_bound(-)],rl[*--u.lower_bound()]):;
        printf("%lld\n",ans+tmp);
    }
    return ;
}