C. Edgy Trees

链接

[https://codeforces.com/contest/1139/problem/C]

题意

给你n个点，n-1个边，无向的。有red和black的。

k表示经过这k个点。可以跨其他点

分析

先算所有的，再减去不符合即可以了。不符合就是都走0的那种

用dfs求联通块并记录该块有多少个点就可以了，看代码吧

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=2e5+10;

const ll mod=1e9+7;

ll po(ll x,ll y){

	ll ba=x,ans=1;

	while(y){

		if(y&1) ans=(ans*ba)%mod;

		ba=(ba*ba)%mod;

		 y>>=1;

	}

	return ans;

}

vector<int> ve[N];

bool vis[N];

ll cnt;

void dfs(int i){

	if(vis[i]) return;

	vis[i]=1;

	cnt++;

	for(int j=0;j<ve[i].size();j++)

	dfs(ve[i][j]);

}

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	//freopen("in.txt","r",stdin);

	ll n,k;

        cin>>n>>k;

		int u,v,x;

		memset(vis,0,sizeof(vis));

		for(int i=1;i<n;i++){

			cin>>u>>v>>x;

			if(x==0)

			ve[u].push_back(v),ve[v].push_back(u);

		}

		ll sum=po(n,k);

		for(int i=1;i<=n;i++)

		{

			cnt=0;

			if(!vis[i])

			{

				dfs(i);

			  sum-=po(cnt,k);

			  sum+=mod;

			  sum%=mod;

			}

		}

		cout<<sum<<endl;

	return 0;

}

巴特西

C. Edgy Trees

链接

题意

分析

代码

最新文章

热门文章