Preface
这里放的是几个最近做过的菜鸡 dp，如果您早就爆切过它们，请尽情嘲讽作者。
CF543D Road Improvement
既然题目要求以每个节点作为根，我们就大力换根。先写出 naive 的初始状态和转移：
设 (f_u) 为 (u) 子树内修路的方案数，则 (f_u=prodlimits_{vin son(u)}(f_v+1))。
意思是每条连向子树的边修的话递归下去 (f_v) 种，不修的话下面只能全修共 (1) 种。
考虑如何换根。
换根 dp 的常见套路是去除父亲的影响后更新儿子，表现在此题上就是要将 (f_u) 除去变为根的儿子 (v) 的 ((f_v+1))。由于直接乘逆元有风险，所以我们记录前/后缀积。
const int N=2000010,p=1000000007;
int n;
LL f[N],g[N];
struct Edge {
int to,nxt;
}e[N<<1];
int hd[N],cnt;
il void ade(int u,int v){
e[++cnt].to=v,e[cnt].nxt=hd[u],hd[u]=cnt;
}
void DFS(int u,int ff){
f[u]=1;
for(rg int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff){
DFS(v,u),f[u]=f[u]*(f[v]+1)%p;
}
}
}
vector<LL> pre[N],suf[N];
void DFS2(int u,int ff){
g[u]=1;
for(rg int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
g[u]=g[u]*(f[v]+1)%p;
if(v!=ff){
pre[u].pub(f[v]+1),suf[u].pub(f[v]+1);
}
}
for(rg int i=1;i<pre[u].size();i++){
pre[u][i]=pre[u][i]*pre[u][i-1]%p;
}
for(rg int i=suf[u].size()-2;i>=0;i--){
suf[u][i]=suf[u][i]*suf[u][i+1]%p;
}
int s=0;
for(rg int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff){
f[u]=(ff?f[ff]+1:1);
if(s>0)f[u]=f[u]*pre[u][s-1]%p;
if(s<suf[u].size()-1)f[u]=f[u]*suf[u][s+1]%p;
DFS2(v,u),s++;
}
}
}
signed main(){
Read(n);
for(rg int i=2,ff;i<=n;i++){
Read(ff),ade(ff,i),ade(i,ff);
}
DFS(1,0),DFS2(1,0);
for(rg int i=1;i<=n;i++)cout<<g[i]<<" ";
return 0;
}
P4284 [SHOI2014]概率充电器
求期望是假的，因为每个节点的贡献都是 (1)。
一个节点的来电方向可能是父亲，不好维护，于是继续大力换根。
设 (f_u) 为 (u) 从子树内来电的概率，则 (f_u=q_u+sumlimits_{vin son(u)}((1-f_u) imes f_v imes p_{u,v}))。
意思是 (u) 亮概率为 (q_u)，不亮时从儿子来电概率为 ((1-f_u) imes f_v imes p_{u,v})。
然后大可根据转移暴力换根，此处不再赘述，但请注意 (0) 的处理。
const int N=500010;
int n;dv f[N],q[N],ans;
struct Edge {
int to,nxt;dv wei;
}e[N<<1];
int hd[N],cnt;
il void ade(int u,int v,dv w){
e[++cnt].to=v,e[cnt].wei=w;
e[cnt].nxt=hd[u],hd[u]=cnt;
}
void DFS(int u,int ff){
f[u]=q[u];
for(rg int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;dv w=e[i].wei;
if(v!=ff){
DFS(v,u);
f[u]+=(1-f[u])*f[v]*w;
}
}
}
void DFS2(int u,int ff){
for(rg int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;dv w=e[i].wei;
if(v!=ff){
dv p=1-f[v]*w;
if(fabs(p)<=eps){
DFS2(v,u);continue;
}
f[v]+=(1-f[v])*(f[u]-f[v]*w)/p*w;
DFS2(v,u);
}
}
}
int main(){
Read(n);
for(rg int i=1,u,v;i<n;i++){
dv w;Read(u),Read(v),scanf("%lf",&w);
ade(u,v,w/100),ade(v,u,w/100);
}
for(rg int i=1;i<=n;i++){
scanf("%lf",&q[i]),q[i]/=100;
}
DFS(1,0),DFS2(1,0);
for(rg int i=1;i<=n;i++)ans+=f[i];
printf("%.6lf
",ans);
KafuuChino HotoKokoa
}
P3233 [HNOI2014]世界树
是一道著名的虚树毒瘤题。
想要满足题目条件，有一个巧妙的方法：先将整棵树划给根所属议事处，然后向下搜索，对于两个议事处之间的路径，找到分界点，将其子树分离。
如果我说得不清楚，那么可以看以下染色过程（其中粗点为议事处，颜色代表所属议事处）：
此题有亿些细节，现罗列如下：
1.处理每个点最近的议事处，这个可以套路两次搜索完成，不过要注意编号的要求。
2.找分界点可以用倍增，注意边界条件的处理。
3.题目没有保证 (1) 不是议事处，建虚树需要小心。
4.!@#%&(#...
const int N=300010,L=18;
int n,q,m,h[N],idx[N],used[N],ans[N];
int dep[N],fa[N][19],siz[N],dfn[N],tot;
struct Edge {
int to,nxt;
}e[N<<1];
int hd[N],cnt;
il void ade(int u,int v){
e[++cnt].to=v,e[cnt].nxt=hd[u],hd[u]=cnt;
}
void DFS(int u,int ff){
dep[u]=dep[ff]+1,fa[u][0]=ff,siz[u]=1,dfn[u]=++tot;
for(rg int i=1;i<=L;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(rg int i=hd[u];i;i=e[i].nxt){
int v=e[i].to;
if(v!=ff){
DFS(v,u),siz[u]+=siz[v];
}
}
}
il int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(rg int i=L;i>=0;i--){
if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
}
if(u==v)return u;
for(rg int i=L;i>=0;i--){
if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
il int Dis(int u,int v){
return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
vector<int> g[N];
il void add(int u,int v){
g[u].push_back(v);
}
int st[N],tp;
il void Insert(int u){
if(!tp){
st[++tp]=u;
return;
}
int l=LCA(st[tp],u);
while(tp>1&&dep[st[tp-1]]>dep[l]){
add(st[tp-1],st[tp]),tp--;
}
if(dep[st[tp]]>dep[l])add(l,st[tp--]);
if(!tp||st[tp]!=l)st[++tp]=l;
st[++tp]=u;
}
il bool cmp(const int &u,const int &v){
return dfn[u]<dfn[v];
}
il void Init(){
Read(m);
for(rg int i=1;i<=m;i++){
Read(h[i]),idx[i]=h[i],used[h[i]]=1;
}
sort(h+1,h+1+m,cmp);
if(!used[1])Insert(1);
for(rg int i=1;i<=m;i++)Insert(h[i]);
while(--tp)add(st[tp],st[tp+1]);
}
//f[i].fi/se:最近议事处的距离与编号
pii f[N];
void GetF1(int u){
if(used[u])f[u]=mkp(0,u);
else f[u]=mkp(INF,0);
for(rg int i=0;i<g[u].size();i++){
int v=g[u][i];
GetF1(v);
f[u]=min(f[u],mkp(f[v].fi+dep[v]-dep[u],f[v].se));
}
}
void GetF2(int u){
for(rg int i=0;i<g[u].size();i++){
int v=g[u][i];
f[v]=min(f[v],mkp(f[u].fi+dep[v]-dep[u],f[u].se));
GetF2(v);
}
}
void GetAns(int u){
int fu=f[u].se;
for(rg int i=0;i<g[u].size();i++){
int v=g[u][i],fv=f[v].se;
if(fu!=fv){
int dis=dep[fv]-(Dis(fu,fv)-(fu<fv))/2;
for(rg int i=L;i>=0;i--){
if(dep[fa[v][i]]>=dis)v=fa[v][i];
}
ans[fu]-=siz[v],ans[fv]+=siz[v];
}
GetAns(g[u][i]);
}
}
void Clear(int u){
for(rg int i=0;i<g[u].size();i++)Clear(g[u][i]);
ans[u]=used[u]=0,g[u].clear();
}
int main(){
Read(n);
for(rg int i=1,u,v;i<n;i++){
Read(u),Read(v),ade(u,v),ade(v,u);
}
DFS(1,0);
Read(q);
while(q--){
Init();
GetF1(1),GetF2(1);
ans[f[1].se]=siz[1];
GetAns(1);
for(rg int i=1;i<=m;i++)cout<<ans[idx[i]]<<" ";
puts(""),Clear(1);
}
return 0;
}