树上问题
开题顺序： \(ALFBD\)
\(A\) luogu P2515 [HAOI2010] 软件安装
\(B\) CF494D Birthday
-
将式子拆成 \(2\sum\limits_{x \in \operatorname{Subtree}(v)}dis_{u,x}^{2}-\sum\limits_{i=1}^{n}dis_{u,i}^{2}\) 的形式。
-
\(\sum\limits_{i=1}^{n}dis_{u,i}^{2}\) 换根 \(DP\) 加完全平方公式是容易维护的。
-
将前面的式子拆开，有 \(dis_{u,x}^{2}=(dis_{1,x}+dis_{1,u}-2dis_{1,\operatorname{LCA}(u,x)})^{2}=dis_{1,u}^{2}+dis_{1,x}^{2}+4dis_{1,\operatorname{LCA}(u,x)}^{2}+2dis_{1,u}dis_{1,x}-4dis_{1,u}dis_{{1,\operatorname{LCA}(u,x)}}-4dis_{1,x}dis_{{1,\operatorname{LCA}(u,x)}}\) 。
-
将常量 \(u\) 提出去，需要额外处理出 \(\sum\limits_{y \in Subtree(x)}dis_{1,y},\sum\limits_{y \in Subtree(x)}dis_{1,y}^{2}\) 。
-
剩下的部分涉及 \(\operatorname{LCA}\) 的求解，需要进行分讨。
- 当 \(u \notin \operatorname{Subtree}(v)\) 时是容易维护的。
- 当 \(u \in \operatorname{Subtree}(v)\) 时，发现 \(v \to u\) 这条链上的点作为 \(\operatorname{LCA}\) 时难以进行统计答案，需要将式子变形成 \(\sum\limits_{i=1}^{n}dis_{u,i}^{2}-2\sum\limits_{x \notin \operatorname{Subtree}(v)}dis_{u,x}^{2}\) ，然后完全平方公式展开即可。
点击查看代码
const ll p=1000000007; struct node { ll nxt,to,w; }e[200010]; ll head[100010],fa[100010],siz[100010],dep[100010],dis[100010],son[100010],top[100010],f[2][100010],g[2][100010],num[2][100010],n,cnt=0; void add(ll u,ll v,ll w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void dfs1(ll x,ll father) { siz[x]=1; fa[x]=father; dep[x]=dep[father]+1; num[0][x]=dis[x]; num[1][x]=dis[x]*dis[x]%p; for(ll i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=father) { dis[e[i].to]=(dis[x]+e[i].w)%p; dfs1(e[i].to,x); siz[x]+=siz[e[i].to]; son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x]; num[0][x]=(num[0][x]+num[0][e[i].to])%p; num[1][x]=(num[1][x]+num[1][e[i].to])%p; f[0][x]=(f[0][x]+f[0][e[i].to]+siz[e[i].to]*e[i].w%p)%p; f[1][x]=(f[1][x]+f[1][e[i].to]+2*e[i].w%p*f[0][e[i].to]%p+e[i].w*e[i].w%p*siz[e[i].to]%p)%p; } } } void dfs2(ll x,ll id) { top[x]=id; for(ll i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa[x]) { g[0][e[i].to]=(g[0][x]+(n-2*siz[e[i].to]+p)*e[i].w%p)%p; g[1][e[i].to]=(g[1][x]+e[i].w*e[i].w%p*(n-2*siz[e[i].to]+p)%p)%p; g[1][e[i].to]=(g[1][e[i].to]+2*e[i].w%p*((g[0][x]-2*f[0][e[i].to]%p-e[i].w*siz[e[i].to]%p+2*p)%p))%p; dfs2(e[i].to,(e[i].to==son[x])?id:e[i].to); } } } ll lca(ll u,ll v) { while(top[u]!=top[v]) { if(dep[top[u]]>dep[top[v]]) u=fa[top[u]]; else v=fa[top[v]]; } return dep[u]<dep[v]?u:v; } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif ll m,u,v,w,rt,ans=0,i; cin>>n; for(i=1;i<=n-1;i++) { cin>>u>>v>>w; add(u,v,w); add(v,u,w); } dfs1(1,0); g[0][1]=f[0][1]; g[1][1]=f[1][1]; dfs2(1,1); cin>>m; for(i=1;i<=m;i++) { cin>>u>>v; rt=lca(u,v); if(rt==v) { w=(dis[u]-dis[v]+p)%p; ans=(g[1][v]-f[1][v]+2*w%p*(g[0][v]-f[0][v]+p)%p+w*w%p*(n-siz[v])%p+p)%p; ans=(g[1][u]-2*ans%p+p)%p; } else { ans=(dis[u]*dis[u]%p*siz[v]%p+num[1][v]+2*dis[u]%p*num[0][v]%p)%p; ans=(ans+4*dis[rt]%p*dis[rt]%p*siz[v]%p)%p; ans=(ans-4*dis[u]%p*dis[rt]%p*siz[v]%p+p)%p; ans=(ans-4*dis[rt]%p*num[0][v]%p+p)%p; ans=(ans*2%p-g[1][u]+p)%p; } cout<<ans<<endl; } return 0; }
\(C\) luogu P4757 [CERC2014] Parades
\(D\) [ARC101E] Ribbons on Tree
-
考虑正难则反，统计不合法的数量。具体地，设 \(F(S)\) 表示断掉 \(S\) 中的边后的方案数，则有 \(\sum\limits_{S \subseteq E}(-1)^{|S|}F(S)\) 即为所求。
-
断掉这些边后原树分成了若干个大小为偶数的连通块，每个连通块内部两两配对，设大小为 \(2siz\) 则其内部的方案数为 \(\prod\limits_{i=1}^{siz}(2siz-1)\) ，记为 \(h_{siz}\) 。
-
不妨统计以 \(x\) 为根的子树内 \(x\) 所在连通块大小为 \(i\) 时子树内部的贡献 \(f_{x,i}\)（包括容斥系数在内）。
-
转移时考虑 \((x,y)\) 这条边是否断掉，分别有 \(\begin{cases} f_{x,i}' \gets -f_{x,i}f_{y,j}h_{j} \\ f'_{x,i+j} \gets f_{x,i}f_{y,j} \end{cases}\) ，需要辅助数组进行转移。
-
最终，有 \(\sum\limits_{i=1}^{n}[i \bmod 2=0] \times f_{1,i}h_{i}\) 即为所求。
点击查看代码
const int p=1000000007; struct node { int nxt,to; }e[10010]; int head[5010],siz[5010],h[5010],f[5010][5010],g[5010],cnt=0; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x,int fa) { siz[x]=1; f[x][1]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x); for(int j=1;j<=siz[x]+siz[e[i].to];j++) g[j]=0; for(int j=1;j<=siz[x];j++) { for(int k=1;k<=siz[e[i].to];k++) { g[j+k]=(g[j+k]+1ll*f[x][j]*f[e[i].to][k]%p)%p; g[j]=(g[j]-1ll*f[x][j]*f[e[i].to][k]%p*h[k]%p+p)%p; } } siz[x]+=siz[e[i].to]; for(int j=1;j<=siz[x];j++) f[x][j]=g[j]; } } } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,u,v,ans=0,i; cin>>n; h[0]=1; for(i=2;i<=n;i++) { cin>>u>>v; add(u,v); add(v,u); if(i%2==0) h[i]=1ll*h[i-2]*(i-1)%p; } dfs(1,0); for(i=2;i<=n;i+=2) ans=(ans+1ll*f[1][i]*h[i]%p)%p; cout<<ans<<endl; return 0; }