9.26

以后可能会在每次考试后(当然极大概率咕咕咕)找一道题讲讲其实是三道题太多了

那么既然量减了,质量就会提上去了也不一定,一次可能会根据某一道题说些思路

反正也没人看,随便写一些留着自己用好了

　　于是本期节目为您带来:换根dp

　　这东西好像考了两三次了,每次都稍恶心,关键是转移难写

　　判断它是个换根dp:

　　　　1.时间复杂度$\Theta(n)$的(或许$\Theta(nlogn)$也可以?),暴力一般是$\Theta(n^2)$的

　　　　2.考虑dp状态与子树有关系的,一般来说是求$ans[i]$需要在以$i$为根的树上统计答案

　　　　3.带补充...

　　我知道这是个换根dp了,然后呢?:

　　　　通常来说换根dp是需要$2+$次dfs的,并且这几次dfs求的都不一样,最后一次dfs通过前一次或几次的dfs求出的各种变量,让答案从父节点向儿子节点转移

上例题:

　　randomwalking form 模拟测试52(b)

　　首先从数据范围推测复杂度,应该是个$\Theta(n)$,最多加个$log$的对吧?

　　我们可以认为一个点的答案应该是(所有它能到的点的贡献和+它的点权)/它的度

　　即为(它父亲的贡献+所有它儿子的贡献和+它的点权)/它的度

　　于是我们会发现这很换根dp

　　那么考虑我们应该怎么切掉这道题

　　我们先定义$son[i]$为一个点的子树以及它本身对$ans[i]$的贡献

　　这显然是可以通过一次dfs求出来的

　　同时我们也就有了$ans[1]$

　　考虑如何由父节点将答案转移至儿子节点

　　对于一个父亲节点,它的答案组成是:

　　$它父亲的贡献+它所有儿子的贡献/它的度+它的点权$

　　对于一个儿子节点,它的答案组成是:

　　$它父亲的贡献+它所有儿子的贡献/它的度+它的点权$

　　那么我们把它的父亲的贡献减去父亲的点权*父亲的度即为:

　　　　$父亲的父亲的贡献+它所有兄弟的贡献+它的贡献$

　　将这个值减去它的子树,即为:

　　　　在以它为根的树中,它以前的父亲的子树对它以前的父亲的贡献

　　将这个值除它以前的父亲现在的儿子数,即为:

　　　　它以前的父亲现在的子树的贡献

　　设这个值为res,我们再考虑其他贡献

　　于是之前的$son[i]$可以被理解为:

　　　　除去它以前的父亲的子树的贡献后,其他儿子对它的贡献+它的点权

　　将son[i]*(度数-1)再减去它的点权

　　加上res即为它所有能到的所有点的贡献

　　再除以它的度,加上它的点权即为它的$ans$

　　于是就有了转移,上代码:

#include<iostream>
#include<cstdio> using namespace std; #define int long long #define cin(k) scanf("%lld",&k) const int maxn=1e6+5; double ans[maxn],son[maxn]; struct road{ int e,nt; }r[maxn<<1]; int nt[maxn],tot; int a[maxn],n; double minn;int bj; int v[maxn],du[maxn]; int sondu[maxn]; void dfs(int k) { double tmp=0; v[k]=1; for(int q=nt[k];q;q=r[q].nt) if(!v[r[q].e]) {sondu[k]++;dfs(r[q].e);tmp+=son[r[q].e];} if(sondu[k])tmp/=sondu[k]; tmp+=a[k]*1.0; son[k]=tmp; v[k]=0; } void getans(int k) { v[k]=1; for(int q=nt[k];q;q=r[q].nt) if(!v[r[q].e]) { double res=ans[k]; res-=