#C241021B. 仓皇逃跑
标签（Label）
- 动态规划
- 容斥原理
- 状态压缩
- 逆向思维
网址（Website）
题解（Solution）
Subtask 分析
肯定会考虑到状态压缩。
Subtask 1：
容易推出，设路径长度为 $l$，则答案为 $k^{n-1-l} \times (k^l - k)$。
$\qquad$ 解释：这里 $k^{n-1-l}$ 表示不在路径上的边颜色选择的方案数，$k^l - k$ 表示路径上颜色的选择方案数（排除全部颜色相同的情况）。
Subtask 2：
还是容斥，正向我想出来之后 $\text{WA}$ 了，反向想要简单得多。$n-1$ 条边随便选的方案数是 $k^{n-1}$，一条路径全部相同的方案数是 $k^{n-l}$，两条路径就考虑去掉重合的方案数。即先分别减去两条路径颜色全部相同的方案数（令路径长度分别为 $l_1, l_2$），再加上两条路径所有边颜色均相同的方案数 $k^{n-l_1-l_2+l_\text{重合}}$，就是最后的答案。直接 $\text{dfs}$ 可以轻易求出重合的边的长度。
$\qquad$ 解释：通过容斥原理，先考虑所有可能的组合，然后减去重复计算的部分，最后加上多减去的部分。
Subtask 3：
和 Subtask 1 的一样，$\prod{(\text{每条路径的贡献})} \times {\text{不在路径上的边颜色随便选的贡献}}$。
$\qquad$ 解释：每条路径的贡献乘起来，再乘以不在路径上的边颜色选择的方案数。
Subtask 4：
直接暴力跑即可，枚举每条边的颜色。
$\qquad$ 解释：由于数据量可能不大，直接枚举所有可能的颜色组合。
Subtask 5：
从 Subtask 2 可以顺带推出，考虑状态压缩枚举 $m$ 条边是否存在，由容斥原理得如果路径条数数是偶数，就从答案中减去计算出来的方案数，否则就加上方案数。每次方案数的计算还是和 Subtask 2 中 $k^{n-l_1-l_2+l_\text{重合}}$ 类似，即 $k^{n-\vert E_1 \bigcup E_2 \bigcup \cdots \bigcup E_c \vert}$，其中 $c$ 表示路径条数，$E_i$ 表示第 $i$ 条路径的边集（应该不会有人不知道 $\vert E_i \vert$ 表示的是集合的大小吧？）。
$\qquad$ 时间复杂度：$O(nm2^m)$。
$\qquad$ 解释：通过状态压缩枚举边的存在性，利用容斥原理计算所有可能的路径组合，然后根据路径数量的奇偶性决定是加还是减方案数。
出题者题解
算法分析
Subtask 1
首先合法路径上至少有两条边颜色不同，这不太好统计，我们可以反过来想：
合法方案数 = 总方案数 - 不合法的方案数
总方案数显然是 $k^{n-1}$，考虑计算不合法方案数。
先考虑 $m=1$ 的情况：
显然，不合法方案的这一条路径上的颜色都是相同的，我们就想到像缩点一样，把这一条路径的边缩成一条边，这样不合法方案数就好算了，设这一条路径包含 $c$ 条边，则不合法方案数为 $k^{n-c}$。
Subtask 1+3
考虑树上差分，知道每条边被算了几次，没算的边拎出来，记为 $cnt$。对于一条路径 $u,v$，合法情况就是 $k^{dis(u,v)}-k$，全部相乘，最后再乘上 $k^{cnt}$。
Subtask 4
直接暴搜每条边，统计答案。
满分做法
还是接着最早的思路想，来考虑不合法的方案。
如果 $m \geq 2$，这样算会重复计算多条路径同时不合法的方案，我们发现 $n \leq 60, m \leq 15$，于是可以直接暴力枚举容斥。
具体来说，就是枚举不合法路径的集合 $S$，对于每条路径，把它所有边合并到某一条边上（如果路径有相交，当然是合并成一条边了）。然后统计合并后的边数 $cnt$，当 $|S|$ 为偶数，让答案加上 $cnt$，当 $|S|$ 为奇数，让答案减去 $cnt$。枚举路径集合可以直接状态压缩，合并可以用并查集实现，时间复杂度
为 $O(nm2^m)$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 128;
const int S = (1<<16);
bool ST;
vector<int> ft[N],e[N];
P road[N];
int n,m,k,ans;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
int fa[N];inline int find(int x){
if(fa[x]==x) return x;
return fa[x] = find(fa[x]);
}
int dep[N],f[N];
void dfs_dep(int x,int F){
dep[x] = dep[F]+1, f[x]=F;
for(auto y:ft[x]) if(y^F) dfs_dep(y,x);
}
int bas[N];
void Solve(){
n = rd(), m = rd(), k = rd();
For(i,1,n-1){
int x = rd(), y = rd();
ft[x].emplace_back(y);
ft[y].emplace_back(x);
}For(i,1,m) road[i] = {rd(), rd()};
dfs_dep(1,0);
For(i,1,m){
int x,y;tie(x,y)=road[i];
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) e[i].emplace_back(x),x=f[x];
while(x!=y) e[i].emplace_back(x),e[i].emplace_back(y),x=f[x],y=f[y];//记录每条路经
}
bas[0] = 1;For(i,1,n) bas[i] = bas[i-1] * k % mod;
ans = bas[n-1];
For(s,1,(1<<m)-1){
int c = __builtin_popcountll(s);
iota(fa,fa+n+1,0);
int all=0;
For(i,1,m){//枚举每一条路径
if((s>>(i-1))&1){
For(j,1,(int)e[i].size()-1){
int fx = find(e[i][0]);
int fy = find(e[i][j]);
fa[fx] = fy;
}
}
}For(i,2,n) all+=fa[i]==i;
if(c&1) add(ans, mod-bas[all]);
else add(ans, bas[all]);
}printf("%lld\n",ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
int T = 1, Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
