cf757F Team Rocket Rises Again (dijkstra+支配树)

我也想要皮卡丘

跑一遍dijkstra，可以建出一个最短路DAG（从S到任意点的路径都是最短路），然后可以在上面建支配树

并不会支配树，只能简单口胡一下在DAG上的做法

建出来的支配树中，某点的祖先集就是从S到该点的必经点集，也就是说，炸掉某点，这个子树都会变得angryunhappy

大概就是按拓扑序来建这个树，每条边(u,v)是要把fa[v]=lca(u,fa[v])，等到v的入度为零时，再用最终的fa[v]连到v上，然后给v做以后求lca时倍增的预处理

最后dfs算出来除S点的最大的子树大小就是答案

 #include<bits/stdc++.h>

 #define pa pair<ll,int>

 #define CLR(a,x) memset(a,x,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int maxn=2e5+,maxm=3e5+;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 struct Edge{

     int a,b,l,ne;

 }eg[maxm*];

 int egh[maxn],ect;

 int N,M,S;

 int fa[maxn][],bro[maxn],sh[maxn],dep[maxn];

 int siz[maxn],ans,ine[maxn];

 ll dis[maxn];

 priority_queue<pa,vector<pa>,greater<pa> > q;

 queue<int> q2;

 bool flag[maxn];

 inline void adeg(int a,int b,int c){

     eg[++ect].a=a;eg[ect].b=b;eg[ect].l=c;

     eg[ect].ne=egh[a];egh[a]=ect;

 }

 inline void dijkstra(){

     CLR(dis,);

     dis[S]=;q.push(make_pair(,S));

     while(!q.empty()){

         int p=q.top().second;q.pop();

         if(flag[p]) continue;

         flag[p]=;

         for(int i=egh[p];i;i=eg[i].ne){

             int b=eg[i].b;

             if(dis[b]>dis[p]+eg[i].l){

                 dis[b]=dis[p]+eg[i].l;

                 q.push(make_pair(dis[b],b));

             }

         }

     }

 }

 int getlca(int x,int y){

     if(dep[x]<dep[y]) swap(x,y);

     for(int i=log2(dep[x]-dep[y]);i>=&&dep[x]!=dep[y];i--){

         if(fa[x][i]&&dep[fa[x][i]]>=dep[y])

             x=fa[x][i];

     }

     if(x==y) return x;

     for(int i=log2(dep[x]);i>=;i--){

         if(fa[x][i]!=fa[y][i])

             x=fa[x][i],y=fa[y][i];

     }

     return fa[x][];

 }

 void dfs(int x){

     siz[x]=;

     for(int i=sh[x];i;i=bro[i]){

         dfs(i);

         siz[x]+=siz[i];

     }

     if(x!=S) ans=max(ans,siz[x]);

 }

 int main(){

     //freopen("","r",stdin);

     int i,j,k;

     N=rd(),M=rd();S=rd();

     for(i=;i<=M;i++){

         int a=rd(),b=rd(),c=rd();

         adeg(a,b,c);adeg(b,a,c);

     }

     dijkstra();

     for(i=;i<=ect;i++){

         int a=eg[i].a,b=eg[i].b;

         if(dis[a]+eg[i].l==dis[b]){

             ine[b]++;

         }

     }

     q2.push(S);dep[S]=;

     while(!q2.empty()){

         int p=q2.front();q2.pop();

         for(i=egh[p];i;i=eg[i].ne){

             int b=eg[i].b;

             if(eg[i].l+dis[p]==dis[b]){

                 fa[b][]=fa[b][]?getlca(p,fa[b][]):p;

                 ine[b]--;

                 if(!ine[b]){

                     dep[b]=dep[fa[b][]]+;

                     for(j=;fa[b][j]&&fa[fa[b][j]];j++)

                         fa[b][j+]=fa[fa[b][j]][j];

                     q2.push(b);

                 }

             }

         }

     }

     for(i=;i<=N;i++){

         // printf("%d %d\n",i,fa[i][0]);

         if(i==S||!fa[i][]) continue;

         bro[i]=sh[fa[i][]],sh[fa[i][]]=i;

     }

     dfs(S);

     printf("%d\n",ans);

     return ;

 }