[2018.10.23 T1] 전쟁

링크 없 음
전쟁.
[제목 설명]
인 류 는 화성 에서 식민지 가 날로 발달 하여 그들 사이 에 자 연 스 럽 게 여러 개의 교통 운송 도 로 를 구축 하여 나무 모양 구 조 를 형성 했다.
구체 적 으로 말 하면 인 류 는 화성 에 이미 n - n 개의 식민 지 를 가지 고 있 으 며, 이 n - n 개의 식민 지 는 n - 1 - n - 1 개의 변 으로 연결 되 어 있다 는 것 을 번호 1 ∼ n 1 \ sim n 1 ∼ n 으로 표시 한다.
동시에, 번 호 는 i 식민지 가 일정한 문명 포 인 트 를 가지 고 있 음 w i wi wi, 그리고 w i = i wi=i wi​=i。두 식민지 u, v u, v u, v 는 교류 하고 문명 가 치 를 형성 할 수 있다.× w v w_u×w_v wu​×wv, 연결 되 지 않 는 식민 지 는 문명 적 가 치 를 가 질 수 없다.화성의 문명 가 치 는 모든 식민지 에서 u, v u, v u, v 에 대한 문명 가치 의 합 이다.
서기 2333 2333 2333 년 에 외계 문명 이 화성 을 공격 했다.이 큰 재난 으로 인해 일부 식민지 들 은 여러 차례 연이어 진 행 된 전쟁 에서 파괴 되 었 고 모두 m m 의 전쟁 을 진 행 했 으 며 모든 전쟁 에서 여러 개의 식민지 가 파괴 되 었 다.파 괴 된 식민지 에는 대량의 방사능 이 남아 있어 한 치 의 풀 도 자라 지 않 고 지나 갈 수도 없고 다른 식민지 와 교류 할 수도 없다.전 세 계 는 전대미문의 위기 에 빠 졌 다.
최 악의 계획 을 세우 기 위해 서 는 전쟁 이 발발 하기 전 (식민지 가 파괴 되 지 않 았 을 때) 화성의 문명 가치 와 매 전투 후 화성 에 현존 하 는 문명 가 치 를 정확하게 계산 할 수 있 기 를 바란다.
【 입력 】
첫 번 째 줄 의 두 정수: n, m, m, m 는 각각 식민지 개수 와 전쟁 장 수 를 나타 낸다.
두 번 째 줄 n - 1 n - 1 n - 1 개의 정수, i i 개의 수 f i fi fi 대표 식민지 i + 1 i + 1 i + 1 과 f i fi fi 는 도로 (0 < f i ≤ i) (0 < f i ≤ i) (0 < fi ≤ i) 가 있다.
다음은 m m 줄 이 있 습 니 다.
i i 행 의 첫 번 째 수 는 정수 k k k 이 고 그 다음 에 k k k 개 수 는 각각 i i 시간 에 파 괴 된 식민지 번 호 를 대표 한다.
【 출력 】
모두 m + 1m + 1 m + 1 줄 의 출력 이 있 습 니 다.
첫 번 째 줄 은 0 0 0 시 에 출력 되 는 답 입 니 다.
제2 2 ~ m + 1m + 1 m + 1 행 에 각각 하나의 정수 s u m sum 을 출력 하 는 것 은 i - 1 i - 1 i - 1 시간 후 (즉, 일부 식민지 가 i - 1 시간 에 파 괴 된 후) 의 답 을 나타 낸다.(주: 정 답 은 (1 0 9 + 7 10 ^ 9 + 7 109 + 7) 모델 링)
[샘플 입력]
3 2 1 2 1 2 1 3
[출력 사례]
11 0 0
[힌트]
【 데이터 범위 】
30% 30 \ \% 30% 의 데이터: n ≤ 200 n ≤ 200 대 60% 60 \ \% 60% 의 데이터: n ≤ 2000 n ≤ 2000 대 100% 100 \ 100% 의 데이터: n ≤ 1 0 6, m ≤ n ≤ 10 ^ 6, m ≤ n ≤ 106, m ≤ n ≤ 106, m ≤ n
해제
오프라인 삭제 작업 은 거꾸로 삽입 작업 을 합 니 다. 가입 점 후 연결 블록 개수 가 줄 어 들 면 새로운 연결 블록 의 가중치 는 원래 두 개의 연결 블록 의 가중치 와 두 개의 가중치 의 축적 입 니 다.
그래서 우 리 는 강력 히 수집 하여 연결 블록 의 가중치 와 유지 하면 된다.
코드

#include
#define pos add[i][j]
using namespace std;
const int M=1e6+6,mod=1e9+7;
int f[M],ans[M],val[M],n,m,r;
bool gg[M];
char c;
vector<int>add[M],mmp[M];
int read()
{
	for(r=0;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())r=(r<<1)+(r<<3)+c-'0';
	return r;
}
void out(int x)
{
	if(x>9)out(x/10);
	putchar(x%10+'0');
}
int root(int v){return f[v]==v?v:f[v]=root(f[v]);}
void link(int x,int y){if(root(x)==root(y))return;(val[root(y)]+=val[root(x)])%=mod;f[root(x)]=root(y);}
void in()
{
	n=read(),m=read();
	for(int i=2,a;i<=n;++i)a=read(),mmp[a].push_back(i),mmp[i].push_back(a);
	for(int i=1,j,a,b;i<=m;++i)
	for(a=read(),j=1;j<=a;++j)b=read(),add[i].push_back(b),gg[b]=1;
}
void ac()
{
	for(int i=1;i<=n;++i)f[i]=val[i]=i;
	for(int i=1;i<=n;++i)
	if(!gg[i])for(int j=mmp[i].size()-1;j>=0;--j)
	if(!gg[mmp[i][j]]&&root(i)!=root(mmp[i][j]))
	ans[m+1]+=val[root(i)]*val[root(mmp[i][j])],link(i,mmp[i][j]);
	for(int i=m;i;--i)
	{
		ans[i]=ans[i+1];
		for(int j=add[i].size()-1;j>=0;--j)gg[add[i][j]]=0;
		for(int j=add[i].size()-1;j>=0;--j)
		for(int k=mmp[pos].size()-1;k>=0;--k)
		if(!gg[mmp[pos][k]]&&root(mmp[pos][k])!=root(pos))
		(ans[i]+=1ll*val[root(mmp[pos][k])]*val[root(pos)]%mod)%=mod,link(mmp[pos][k],pos);
	}
	for(int i=1;i<=m+1;++i)out(ans[i]),putchar(10);
}
int main(){in(),ac();}