【NOIP模拟】战争

题面

分析

正难则反系列

删除操作很难维护，倒过来，加边维护。并查集同时维护这个集合的祖先和点权和。

合并两个集合的代价就是 sum[x]*sum[y]

但是要注意最后不一定把所有点删完了，所以最后一次删除后的答案要dfs一下联通块特殊求

【然而出题人并没有卡这个..】

代码

  1. #include<bits/stdc++.h>  
  2. using namespace std;  
  3. #define N 1101000  
  4. #define ll long long   
  5. const ll mod=1e9+7;  
  6. ll n,m,k,cnt,pos;  
  7. ll fa[N],sum[N],ans[N],vis[N],mark[N],first[N];  
  8. vector<ll>v[N];  
  9. struct email  
  10. {  
  11.     ll u,v;  
  12.     ll nxt;  
  13. }e[N*4];  
  14. inline ll find(ll x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}  
  15. inline void add(ll u,ll v)  
  16. {  
  17.     e[++cnt].nxt=first[u];first[u]=cnt;  
  18.     e[cnt].u=u;e[cnt].v=v;  
  19. }  
  20. template<class T>  
  21. void read(T &x)  
  22. {  
  23.     x=0;  
  24.     static char c=getchar();  
  25.     while(c<'0'||c>'9') c=getchar();  
  26.     while(c>='0'&&c<='9')  
  27.     x=x*10+c-'0',c=getchar();  
  28. }  
  29.   
  30. inline void merge(int x,int y)  
  31. {  
  32.     pos=(pos+(sum[x]*sum[y])%mod)%mod;  
  33.     fa[y]=x;sum[x]+=sum[y];sum[x]%=mod;  
  34. }  
  35.   
  36. inline void dfs(ll u)  
  37. {  
  38.   
  39.     vis[u]=1;  
  40.     for(ll i=first[u];i;i=e[i].nxt)  
  41.     {  
  42.         ll v=e[i].v;  
  43.         if(vis[v]||mark[v])continue;  
  44.         dfs(v);  
  45.         ll fax=find(u),fay=find(v);  
  46.         merge(fax,fay);  
  47.     }  
  48. }  
  49.   
  50.   
  51. int main()  
  52. {  
  53.     read(n);read(m);  
  54.     for(ll u=2;u<=n;u++)  
  55.     {  
  56.         ll v;  
  57.         read(v);  
  58.         add(u,v);add(v,u);  
  59.     }  
  60.     for(ll i=1;i<=n;i++)sum[i]=i,fa[i]=i;     
  61.     for(ll i=1;i<=m;i++)  
  62.     {  
  63.         ll p;read(k);  
  64.         for(ll j=0;j<k;j++)  
  65.             read(p),mark[p]=1,v[i].push_back(p);  
  66.     }  
  67.     for(ll i=1;i<=n;i++)  
  68.         if(mark[i]==0&&vis[i]==0)  
  69.             dfs(i);  
  70.     ans[m+1]=pos;  
  71.     for(ll x=m;x>=1;x--)  
  72.     {  
  73.         for(ll j=0;j<v[x].size();j++)  
  74.         {  
  75.             ll u=v[x][j];  
  76.             ll fax=find(u);  
  77.             for(int i=first[u];i;i=e[i].nxt)  
  78.             {  
  79.                 int v=e[i].v;  
  80.                 if(mark[v])continue;  
  81.                 ll fay=find(v);  
  82.                 merge(fax,fay);  
  83.             }  
  84.             mark[u]=0;  
  85.         }  
  86.         ans[x]=pos;  
  87.     }  
  88.     for(ll i=1;i<=m+1;i++)  
  89.     printf("%lld ",ans[i]);  
  90. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/NSD-email0820/p/9837537.html