考虑容斥，枚举哪些路径一定不合法即可：$\sum (-1)^{|S|}2^{(n-1)-val_S}$ 。其中 $val_S$ 指 $S$ 中的路径覆盖的边数条数。
因为所有的路径的两个端点满足祖先关系，考虑用 $dp$ 解决这个问题。
令 $dp_{u,i}$ 表示对于所有起点在 $u$ 的子树中的路径，选了一些，满足选出来的这些路径的终点的最小深度为 $i$ 时的容斥系数和。
这里考虑将 $\sum (-1)^{|S|}2^{(n-1)-val_S}$ 拆为 $2^{n-1}\sum (-1)^{|S|}\frac{1}{2^{val_S}}$ ，然后所谓的容斥系数指的 $(-1)^{|S|}\frac{1}{2^{val_S}}$ ，这样就可以很方便的合并了。
直接这样做时间复杂度 $O(n^2)$ ，可以拿到 $36\ pts$ 。
void solve(int u,int fa) {
if(~top[u]) pls(dp[u][top[u]],mod-inv[dep[u]-top[u]]);
pls(dp[u][dep[u]],1);
for(int v:son[u]) if(v!=fa) {
solve(v,u);
lep(i,1,dep[u]) lep(j,1,dep[v]) {
int res=mul(dp[u][i],dp[v][j]);
if(j<dep[v]) res=mul(res,fac[dep[u]-max(i,j)]);
pls(tmp[min(i,j)],res);
}
lep(i,0,n) dp[u][i]=tmp[i],tmp[i]=0;
}
}
答案显然就是 $dp_{1,1}$ 。
（注意到可能有很多条起点为 $u$ 的路径，但是只需要保留最下面的一条（即终点深度最神的），因为乘上容斥系数后上面的全部抵消了。
考虑优化。
考虑另外一种更加整洁的 $O(n^2)$ 做法，即转移的时候枚举目标位置，然后中间这个 if(j<dep[v]) 太丑了，去掉后在最后单独处理 $dp_{u,dep_u}$ 即可。这个 fac[dep[u]-max(i,j)] 也可以拆开。
void solve(int u,int fa) {
if(~top[u]) pls(dp[u][top[u]],mod-inv[dep[u]-top[u]]);
pls(dp[u][dep[u]],1);
for(int v:son[u]) if(v!=fa) {
solve(v,u);
lep(i,1,dep[u]) {
int res=mul(mul(dp[u][i],dp[v][i]),inv[i]);
lep(j,i+1,dep[u]) pls(res,mul(mul(dp[u][j],dp[v][i]),inv[j]));
lep(j,i+1,dep[v]) pls(res,mul(mul(dp[u][i],dp[v][j]),inv[j]));
dp[u][i]=res;
}
lep(i,0,n) dp[u][i]=mul(fac[dep[u]],dp[u][i]);
}
if(u!=1) dp[u][dep[u]]=mul(dp[u][dep[u]],2);
}
接下来，不妨将 $dp_{u,i}$ 重定义为 $dp_{u,i}\cdot \frac{1}{2^i}$ 。那么转移的时候就可以去掉后面的 inv[*] 。
然后就可以发现，$i$ 这个位置，转移就是三种：$u,v$ 都取第 $i$ 位置，$u$ 取第 $i$ 位且 $v$ 取一个后缀和，$v$ 取第 $i$ 位且 $u$ 取一个后缀和。
PKUWC 2018 Minimax 启发了我们线段树合并也可以优化一类有关前缀/后缀和转移的 $dp$ 。不妨考虑用线段树合并来解决此题，然后就做完了。
合并过程可以见 merge 函数。
const int N=5e5+5;
int n,m,inv[N],fac[N],dep[N],top[N];
std::vector <int> son[N];
inline void init() {
fac[0]=inv[0]=1;
int inv2=modpow(2,-1);
lep(i,1,n) inv[i]=mul(inv[i-1],inv2),fac[i]=mul(fac[i-1],2);
}
// {{{ Segment_Tree
#define mid ((l+r)>>1)
const int M=2e7+5;
int cnt,rt[N],lc[M],rc[M],sum[M],tag[M];
inline void update(int x,int v) {sum[x]=mul(sum[x],v),tag[x]=mul(tag[x],v);}
inline void pushdown(int x) {if(tag[x]!=1) update(lc[x],tag[x]),update(rc[x],tag[x]),tag[x]=1;}
void modify(int &x,int l,int r,int pos,int val) {
if(!x) x=++cnt,tag[x]=1; pls(sum[x],val);
if(l==r) return void();
pushdown(x);
pos<=mid?modify(lc[x],l,mid,pos,val):modify(rc[x],mid+1,r,pos,val);
}
void _ex_modify(int &x,int l,int r,int pos) {
if(!x) x=++cnt,tag[x]=1;
if(l==r) return sum[x]=mul(sum[x],2),void();
pushdown(x);
pos<=mid?_ex_modify(lc[x],l,mid,pos):_ex_modify(rc[x],mid+1,r,pos);
sum[x]=add(sum[lc[x]],sum[rc[x]]);
}
int query(int x,int l,int r,int pos) {
if(l==r) return sum[x];
pushdown(x);
return (pos<=mid?query(lc[x],l,mid,pos):query(rc[x],mid+1,r,pos));
}
int merge(int x,int y,int l,int r,int s1,int s2) {
if(!x||!y) {
if(!x) return update(y,s1),y;
if(!y) return update(x,s2),x;
}
if(l==r) {
int now=add(add(mul(sum[x],s2),mul(sum[y],s1)),mul(sum[x],sum[y]));
if(!x) x=y;
return sum[x]=now,x;
}
pushdown(x),pushdown(y);
lc[x]=merge(lc[x],lc[y],l,mid,add(s1,sum[rc[x]]),add(s2,sum[rc[y]]));
rc[x]=merge(rc[x],rc[y],mid+1,r,s1,s2);
sum[x]=add(sum[lc[x]],sum[rc[x]]);
return x;
}
// }}
void dfs(int u,int fa) {
dep[u]=dep[fa]+1;
for(int v:son[u]) if(v!=fa) dfs(v,u);
}
void solve(int u,int fa) {
if(~top[u]) modify(rt[u],1,n,top[u],mul(mod-inv[dep[u]-top[u]],inv[top[u]]));
modify(rt[u],1,n,dep[u],inv[dep[u]]);
for(int v:son[u]) if(v!=fa) {
solve(v,u);
rt[u]=merge(rt[u],rt[v],1,n,0,0);
update(rt[u],fac[dep[u]]);
}
if(u!=1) _ex_modify(rt[u],1,n,dep[u]);
}
int u,v;
int main() {
freopen("destiny.in","r",stdin);
freopen("destiny.out","w",stdout);
IN(n);
lep(i,2,n) IN(u,v),son[u].pb(v),son[v].pb(u);
dfs(1,0);
IN(m);
lep(i,1,n) top[i]=-1;
lep(i,1,m) IN(u,v),chkmax(top[v],dep[u]);
init(),solve(1,0);
printf("%d\n",mul(fac[n],query(rt[1],1,n,1)));
return 0;
}
0 条评论