bzoj3991 LCA + set-白红宇

bzoj3991 LCA + set

阅读量：5462 次

发布时间：2019-06-15

本文共 3403 字，大约阅读时间需要 11 分钟。

https://www.lydsy.com/JudgeOnline/problem.php?id=3991

小B最近正在玩一个寻宝游戏，这个游戏的地图中有N个村庄和N-1条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个游戏中宝物经常变化，有时某个村庄中会突然出现宝物，有时某个村庄内的宝物会突然消失，因此小B需要不断地更新数据，但是小B太懒了，不愿意自己计算，因此他向你求助。为了简化问题，我们认为最开始时所有村庄内均没有宝物的

很显然问题的关键在于处理每一次变更的宝藏点的信息，一个容易发现的结论是，只要是从宝藏点出发，无论哪个点出发都能寻找到一条最优的路径，因为行走的路径会是一个环，对于K个宝藏点，行走的路径是1->2,2->3,3->4.........k-1 -> k,k ->1，所以说，对于一条链，每一次变更只要找到这个点插入的前驱pre和后继nxt，插入的时候删除dis(pre,nxt)，加上dis(pre,x) + dis(x,pre)就可以了，删除同理。

问题在于怎么去寻找他的前驱和后继，对于一棵树来说，想要遍历所有的关键点，贪心的想到是和dfs一样走，可以最短的经过一圈所有的关键点，所以我们掏出一手dfs序的前序，对于每一个数字的更改，去寻找他在dfs序里面前后最接近的宝藏点就是他的前驱和后继。

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair
                    
                     #define PIL pair
                     
                      #define PLL pair
                      
                       #define pb push_back#define fi first#define se second typedef vector
                       
                         VI;const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; const int SP = 20;int N,M,K;struct Edge{ int to,next; LL dis;}edge[maxn * 2];int dfn[maxn];int head[maxn],tot;int id;int idx[maxn];LL Dis[maxn];int pa[maxn][SP],dep[maxn];int vis[maxn];set
                        
                         Q;void init(){ Mem(head,-1); tot = 0;}void add(int u,int v,LL w){ edge[tot].to = v; edge[tot].next = head[u]; edge[tot].dis = w; head[u] = tot++;}void dfs(int u,int la){ dfn[u] = ++id; idx[id] = u; pa[u][0] = la; For(i,1,SP - 1) pa[u][i] = pa[pa[u][i - 1]][i - 1]; for(int i = head[u]; ~i; i = edge[i].next){ int v = edge[i].to; if(v == la) continue; dep[v] = dep[u] + 1; Dis[v] = Dis[u] + edge[i].dis; dfs(v,u); }}int lca(int u,int v){ if(dep[u] < dep[v]) swap(u,v); int t = dep[u] - dep[v]; For(i,0,SP - 1) if(t & (1 << i)) u = pa[u][i]; _For(i,SP - 1,0){ int uu = pa[u][i],vv = pa[v][i]; if(uu != vv){ u = uu; v = vv; } } return u == v?u:pa[u][0];}LL DIS(int u,int v){ return Dis[u] + Dis[v] - 2 * Dis[lca(u,v)];}int main(){ Sca2(N,M); init(); For(i,1,N - 1){ int u,v; Sca2(u,v); LL w; Scl(w); add(u,v,w); add(v,u,w); } Dis[1] = 0;id = 0;dfs(1,1); LL ans = 0; Q.insert(0); Q.insert(N + 1); while(M--){ int x; Sca(x); if(vis[x]){ int pre = *--Q.find(dfn[x]),pro = *++Q.find(dfn[x]); if(pre >= 1) ans -= DIS(idx[pre],x); if(pro <= N) ans -= DIS(idx[pro],x); if(pre >= 1 && pro <= N) ans += DIS(idx[pre],idx[pro]); Q.erase(dfn[x]); }else{ Q.insert(dfn[x]); int pre = *--Q.find(dfn[x]),pro = *++Q.find(dfn[x]); if(pre >= 1) ans += DIS(idx[pre],x); if(pro <= N) ans += DIS(idx[pro],x); if(pre >= 1 && pro <= N) ans -= DIS(idx[pre],idx[pro]); } LL z = 0; int s = *++Q.find(0),e = *--Q.find(N + 1); if(s >= 1 && e <= N) z = DIS(idx[s],idx[e]); Prl(ans + z); vis[x] ^= 1; } #ifdef VSCode system("pause"); #endif return 0;}

转载于:https://www.cnblogs.com/Hugh-Locke/p/9762335.html

你可能感兴趣的文章