暂无链接
战争
【题目描述】
人类在火星上的殖民地日渐发达，它们之间自然地构建起了多条交通运输道路，形成一个树状结构。
具体的说，人类在火星上已经有了
n
n
n个殖民地，用编号
1
∼
n
1\sim n
1∼n表示，这
n
n
n个殖民地由
n
−
1
n−1
n−1条边连通。
同时，编号为i殖民地拥有一定的文明点数
w
i
w_i
wi，并且
w
i
=
i
w_i=i
wi=i。两个殖民地
u
,
v
u,v
u,v可以交流并产生文明价值，当且仅当
u
,
v
u,v
u,v连通，交流产生的文明价值为
w
u
×
w
v
w_u×w_v
wu×wv，不连通的殖民地无法产生文明价值。火星的文明价值即为所有殖民地点对
u
,
v
u,v
u,v的文明价值的和。
公元
2333
2333
2333年，外星文明进攻了火星。这一场浩劫导致一些殖民地在许多场先后进行的战争中被破坏，一共进行了
m
m
m场战争，每一场战争有多个殖民地被破坏。破坏后的殖民地残存大量辐射寸草不生，既无法被经过也无法与其他殖民地交流。全球陷入了空前的危机。
为了做好最坏的打算，你希望可以准确计算出战争爆发前(没有殖民地被破坏时)火星的文明价值，以及每轮战斗后，火星现存的文明价值。
【输入】
第一行两个正整数：
n
,
m
n,m
n,m分别表示殖民地个数和战争场数
第二行
n
−
1
n−1
n−1个整数，第
i
i
i个数
f
i
f_i
fi代表殖民地
i
+
1
i+1
i+1与
f
i
f_i
fi有一条道路
(
0
<
f
i
≤
i
)
(0<f_i≤i)
(0<fi≤i)。
接下来依次有
m
m
m行：
第
i
i
i行第一个数为正整数
k
k
k，接下来
k
k
k个数分别代表第
i
i
i时刻被破坏的殖民地编号。
【输出】
一共有
m
+
1
m+1
m+1行输出。
第一行输出在
0
0
0时刻的答案，
第
2
2
2到
m
+
1
m+1
m+1行分别输出一个整数
s
u
m
sum
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
n≤200 对于
60
%
60\%
60%的数据：
n
≤
2000
n≤2000
n≤2000 对于
100
%
100\%
100%的数据：
n
≤
1
0
6
,
m
≤
n
n≤10^6,m≤n
n≤106,m≤n
题解
离线删除操作，倒着做插入操作，加入点后如果联通块个数减少，新联通块的权值即为原来两个联通块的权值之和加上两权值之积。
所以我们大力并查集，维护联通块权值和即可。
代码
#include<bits/stdc++.h>
#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();}
