HDOJ 6795 Little W and Contest(항 전 다 교 2020 제3 차 1005)

http://acm.hdu.edu.cn/showproblem.php?pid=6795 사고방식:tot 2 와 tot 1 은 모든 사람 중 몇 개,몇 개,2 cnt 1[x]과 cnt 2[x]가 x 를 첫째 로 하 는 이 그룹 중 몇 개,몇 개,몇 개,2 를 기록한다.먼저 초기 상태 에서 모든 사람 이 서로 알 지 못 하 는 종 수 를 계산 합 니 다.즉,'x 에서 y 에서 한 명 씩 선택 하고 다른 팀 에서 한 명 을 선택한다'는 상황 은 합병 전에 할 수 있 고 합병 후에 할 수 없 는 것 이다.우 리 는 이런 종 수 를 빼 면 된다.

		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
		rest1 = tot1-cnt1[x]-cnt1[y];//  xy      1  2
		rest2 = tot2-cnt2[x]-cnt2[y];
		
		ans = cnt2[x]*cnt2[y]*(rest1+rest2);
		//x    2，y    2，     1 2
		ans += cnt2[x]*cnt1[y]*rest2;
		//x 2，y 1，     2
		ans += cnt2[y]*cnt1[x]*rest2;
		//x 1，y 2，     2
		
		cnt1[x] = cnt1[y]+cnt1[x];
		cnt2[x] = cnt2[y]+cnt2[x];// x      y  

결 과 를 계산 한 후에 Y 조 의 모든 사람 을 x 조,즉 cnt 1[x]에 cnt 1[y],cnt 2[x]에 cnt 2[y]를 더 하 는 것 을 기억 해 야 합 니 다!코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

template<class T>inline void read(T &x){x=0;char o,f=1;while(o=getchar(),o<48)if(o==45)f=-f;do x=(x<<3)+(x<<1)+(o^48);while(o=getchar(),o>47);x*=f;}
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=b;i--)
#define INF 0x3f3f3f3f
#define cendl printf("
")
ll gcd(ll a,ll b){ while(b^=a^=b^=a%=b); return a; }
//#define INF 0x7fffffff

const int MAXN = 1e5+5;
const int Mod = 1e9+7;
int a[MAXN];
int n;
//      
int par[MAXN];//       
int rk[MAXN];//    ,   (    )          
void init(int n){
	for(int i=1;i<=n;i++){
		par[i]=i;
		rk[i]=0;
	}
} 
int find(int x){//     ，         
	if(par[x]==x) return x;
	else return par[x]=find(par[x]);//           i   
}

ll cnt1[MAXN];
ll cnt2[MAXN];//           1 2
ll tot1,tot2;//  1 2    

ll merge(int x,int y){//                
	ll ans;
	ll rest1,rest2;
	x=find(x);
	y=find(y);
	if(x==y) return 0;//         
	if(rk[x]<rk[y]){
		par[x]=y;//x  y 
		rest1 = tot1-cnt1[y]-cnt1[x];
		rest2 = tot2-cnt2[y]-cnt2[x];//      1 2
		// ans 
		ans = cnt2[x]*cnt2[y]*(rest1+rest2);//x    2，y    2，     1 2 
		ans += cnt2[x]*cnt1[y]*rest2;
		ans += cnt2[y]*cnt1[x]*rest2; 
		
		cnt1[y] = cnt1[y]+cnt1[x];
		cnt2[y] = cnt2[y]+cnt2[x];// x      y  
	}
	else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
		rest1 = tot1-cnt1[x]-cnt1[y];
		rest2 = tot2-cnt2[x]-cnt2[y];
		// ans
		ans = cnt2[x]*cnt2[y]*(rest1+rest2);//x    2，y    2，     1 2
		ans += cnt2[x]*cnt1[y]*rest2;
		ans += cnt2[y]*cnt1[x]*rest2;
		
		cnt1[x] = cnt1[y]+cnt1[x];
		cnt2[x] = cnt2[y]+cnt2[x];// x      y  
	}
	return ans; 
}

void solve(){
	tot1=tot2=0;
	cin>>n;
	init(n); 
	rep(i,1,n){
		cin>>a[i];
		if(a[i]==1) cnt1[i]=1,cnt2[i]=0,tot1++;//           
		else cnt2[i]=1,cnt1[i]=0,tot2++;
	}
	ll res = (tot2*(tot2-1)/2*tot1 + tot2*(tot2-1)*(tot2-2)/2/3);
	//             
	cout<<res%Mod<<endl; 
	int u,v;
	rep(i,1,n-1){
		cin>>u>>v;
		res-=merge(u,v);
		cout<<max(res%Mod,(ll)0)<<endl;
	}
}

int main(){
	int z;
	cin>>z;
	while(z--) solve();
}