제출 #1300889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300889		MuhammadSaram	Šarenlist (COCI22_sarenlist)	C++20	35 / 110	1 ms	576 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7, M = 61;

int dep[M], par[M];
vector<int> nei[M];
int msk[(1<<15)], now[(1<<15)];

void dfs(int u)
{
	for (int i:nei[u])
		if (i!=par[u])
			par[i]=u, dep[i]=dep[u]+1, dfs(i);
}

int lca(int u,int v)
{
	if (dep[u]>dep[v]) swap(u,v);
	while (dep[v]>dep[u]) v=par[v];
	while (u!=v)
		u=par[u], v=par[v];
	return u;
}

signed main()
{
	int n,m,k;
	cin>>n>>m>>k;
	int ans=1, pw[n];pw[0]=1;
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
		ans=ans*k%mod, pw[i]=ans;
	}
	dfs(1);
	for (int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		int p=lca(u,v);
		while (u!=p)
			msk[(1<<i)]|=(1ll<<u), u=par[u];
		while (v!=p)
			msk[(1<<i)]|=(1ll<<v), v=par[v];
	}
	now[0]=1;
	for (int ms=1;ms<(1<<m);ms++)
	{
		int p=ms&-ms;
		now[ms]=now[ms^p];
		if (!(msk[p]&msk[ms^p])) now[ms]=now[ms]*k%mod;
		msk[ms]=msk[ms^p]|msk[p];
		int z=n-1-__builtin_popcountll(msk[ms]);
		ans+=pw[z]*now[ms]%mod;
		if (__builtin_popcount(ms)%2) ans-=pw[z]*now[ms]%mod*2;
		ans=(ans+mod*2)%mod;
	}
	cout<<ans<<endl;
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 65