我日哦 完全忘了前几天才做的星球大战（JSOI2008
这道题还有花椒麻你 告诉你是一棵树 迷惑你是树上算法
正难即反 考虑离线存下点 用并查集维护
先把没有被破坏的点连起来 当两个联通块将要merge的时候 这时总贡献加了他们的权值和之积（根据乘法分配率可得
简直和星球大战一模一样
#include<bits/stdc++.h> #define ll long long #define N 1000005 using namespace std; const int mod=1000000007; struct Edge { int from,to,next; }edge[2*N]; int n,m; int tot,first[N],father[N]; inline void addedge(int x,int y) { tot++; edge[tot].from=x; edge[tot].next=first[x]; edge[tot].to=y; first[x]=tot; } inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } vector <int> attack[N]; bool broken[N]; ll w[N],sum,ans[N]; void merge(int x,int y) { int fx=getfather(x),fy=getfather(y); if(fx!=fy) { father[fx]=fy; sum=(sum+w[fx]*w[fy]%mod)%mod; w[fy]=(w[fx]+w[fy])%mod; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n>>m; for(ll i=1;i<=n;i++) { father[i]=i; w[i]=i; } for(int i=2;i<=n;i++) { int x; cin>>x; addedge(i,x); addedge(x,i); } for(int i=1;i<=m;i++) { int k; cin>>k; for(int j=1;j<=k;j++) { int x; cin>>x; attack[i].push_back(x); broken[x]=true; } } for(int u=1;u<=2*m;u++) //merge现存的边 { int x=edge[u].from,y=edge[u].to; if(broken[x]||broken[y]) continue; merge(x,y); } ans[m+1]=sum; for(int i=m;i>=1;i--) { for(int j=0;j<attack[i].size();j++) { int now=attack[i][j]; broken[now]=false; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(broken[vis]) continue; merge(now,vis); } } ans[i]=sum; } for(int i=1;i<=m+1;i++) cout<<ans[i]<<'\n'; return 0; }