以后可能会在每次考试后(当然极大概率咕咕咕)找一道题讲讲其实是三道题太多了
那么既然量减了,质量就会提上去了也不一定,一次可能会根据某一道题说些思路
反正也没人看,随便写一些留着自己用好了
于是本期节目为您带来:换根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-=a