前言
萌新在高中浅浅接触 OI ,就听说了换根 dp ,奈何当时太菜了,听不懂,所以只能在大学重新学学了
最基础部分
给定一个 n 个点的无根树,问以树上哪个节点为根时,其所有节点的深度和最大?
深度:节点到根的简单路径上边的数量
这个是最经典的换根dp,而且经典到做了这道题你仅仅能了解什么是换根,其他代码照样写不出来。由于这道题太简单了,不写代码。
换根 dp 最广泛的操作就是,两个 dfs ,第一次统计子树内的,第二次转移子树外的。
例题
洛谷 P3047 [USACO12FEB]Nearby Cows G
给你一颗树,询问每个点周围距离小于等于 k 的权值和。
记 fi,j 表示 i 点距离为 k 的权值,那么第一次有一个从子树转移过来的,第二次统计子树外面的。
等等,有重复?
fi,l 与 fj,l−1 是包含关系,然而 fj,l+1 又要从 fi,l 转移过来,但是仅仅如此,倒序然后 fj,l+1+=fi,l−fj,l−1 即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
| #include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<vector> #include<set> #include<map> #include<algorithm>
using namespace std;
const int maxn=1e5+20;
int f[maxn][25]; int n,head[maxn]; int a[maxn],s1ze,k;
struct edge{ int next,to; }e[maxn*2];
void addedge(int next,int to) { e[++s1ze].to=to; e[s1ze].next=head[next]; head[next]=s1ze; }
void dfs1(int t,int fat) { f[t][0]=a[t]; for(int i=head[t];i;i=e[i].next) { int j=e[i].to; if(j==fat) continue; dfs1(j,t); for(int l=1;l<=k;l++) f[t][l]+=f[j][l-1]; } }
void dfs2(int t,int fat) { for(int i=head[t];i;i=e[i].next) { int j=e[i].to; if(j==fat) continue; for(int l=k;l>=2;l--) { f[j][l]+=f[t][l-1]-f[j][l-2]; } f[j][1]+=a[t]; dfs2(j,t); } }
int main() { ios::sync_with_stdio(false); cin>>n>>k; for(int i=1;i<n;i++) { int t1,t2; cin>>t1>>t2; addedge(t1,t2); addedge(t2,t1); } for(int i=1;i<=n;i++) cin>>a[i]; dfs1(1,1); dfs2(1,1); for(int i=1;i<=n;i++) { int ans=0; for(int j=0;j<=k;j++) ans+=f[i][j]; cout<<ans<<"\n"; }
}
|