2020HDU多校第三场 Little W and Contest

题意：给定n个人，第i个人为1 表示是读者，2表示为程序员，ACM赛制是三人一组，规定三人至少有两个为程序员，而且三个人互相不认识。一开始所有人都是互相不认识。然后依次给出n-1条朋友关系(关系满足传递)使得所有人都互相认识。求给出第i条朋友关系时，可以三人一组组队的方案数是多少。答案模1e9+7.

分析:并查集，增加一个新边，对原有方案减少了多少。我们并查集维护一个连通块里2和1的人数各有多少。增加新边相当于要减去从(2,2,1),(2,2,2)这两种的方案。
那么选人左右连通块都是可能会选的：
左边选1的人，右边选2 的人 方案(1,2,2)
左边选2的人，右边选1 的人 方案(1,2,2)
左边选2的人，右边选2 的人 方案(2,2,2)
第三个人的选人集合( cnti-s[x][i]-s[y][i] )

类似题目( https://ac.nowcoder.com/acm/contest/889/E
题解： E https://blog.nowcoder.net/n/860ec8e0ecc1412fae37ce93292b430b

#include<bits/stdc++.h>
#define sscc ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;

const ll mod=1e9+7;
const ll maxn=1e5+5;

ll f[maxn];




ll a[maxn],b[maxn];
ll p[maxn],s[maxn][3];

int get_fa( int x ) { return f[x]==x ? x : f[x]=get_fa(f[x]); } 


int main()
{
    sscc; 

    int t;
    cin>>t;
    while( t-- )
    {
        int n;
        cin>>n;
        ll cnt1=0;
        ll cnt2=0;
        memset(s,0,sizeof(s));
        for( int i=1;i<=n;i++ )
        {
            cin>>p[i];
            int x=p[i];
            f[i]=i;
            if( x==2 ) cnt2++,s[i][2]++;
            else cnt1++,s[i][1]++;
        }


        ll ans=( cnt2*(cnt2-1)/2*cnt1%mod+((cnt2-2)*cnt2*(cnt2-1))/6 )%mod;
        cout<<ans<<"\n";
        int m=n-1;

        while( m-- )
        {
            int x,y;
            cin>>x>>y;
            x=get_fa(x);
            y=get_fa(y);


            ans-=1ll*s[x][1]*s[y][2]*(cnt2-s[y][2]-s[x][2])%mod+
            1ll*s[x][2]*s[y][1]*(cnt2-s[y][2]-s[x][2])%mod+
            1ll*s[x][2]*s[y][2]*(cnt1-s[y][1]-s[x][1])%mod+
            1ll*s[x][2]*s[y][2]*(cnt2-s[y][2]-s[x][2])%mod;

            ans=(ans+4*mod)%mod;

            f[x]=y;
            s[y][1]+=s[x][1];
            s[y][2]+=s[x][2];

            cout<<ans<<"\n";
        }
    }
}