Codeforces 771C：Bear and Tree Jumps
Codeforces 771C：Bear and Tree Jumps
题目链接：http://codeforces.com/problemset/problem/771/C
题目大意：给出一个$n(2 \leqslant n \leqslant 200,000)$个结点的无根树及整数$k(1 \leqslant k \leqslant 5)$，求$\sum f(s,t),(s<t)$，其中$f(s,t)=\lceil \frac{dis(s,t)}{k} \rceil$.
树形DP
设$dis(u,v)$为$u$到$v$的简单路径长度，则$f(u,v)=\lceil \frac{dis(u,v)}{k} \rceil=\frac{dis(u,v)+L(u,v)}{k}$，于是问题就转化为求$\sum dis(u,v)$和$\sum L(u,v)$.
$\sum dis(u,v)$可以很容易求得：任取一结点为根，每条边的贡献为$num[x] \times (n-num[x])$，其中$x$为该边的子结点，$num[x]$为$x$的子树的结点个数.
关键在于求$\sum L(u,v)$.定义$dp[i][j]$为从$i$的子树出发到达$i$结点，简单路径长度模$k$为$j$的个数.设$u$为$v$的父节点，根据$dp[u][i]$和$dp[v][j]$，可以求得包含$u$，$v$结点的路径长模为$(i+j+1)\%k$的路径数为$dp[u][i] \times dp[v][j]$条，从而可以求出相应的$\sum L(x,y)$.转移方程为$dp[u][(i+1)\%k]=dp[u][(i+1)\%k]+dp[v][i]$.
于是$ans=\sum \frac{dis(u,v)+L(u,v)}{k}$，复杂度为$O(nk^2)$
代码如下：
1 #include <iostream> 2 #include <vector> 3 #include <cstring> 4 #define N 200005 5 using namespace std; 6 typedef long long ll; 7 int n,k; 8 ll ans,dp[N][6],sum[N]; 9 vector<int>e[N]; 10 ll dfs(int u,int pre){ 11 dp[u][0]=sum[u]=1; 12 for(int t=0;t<(int)e[u].size();++t){ 13 int v=e[u][t]; 14 if(v!=pre){ 15 sum[u]+=dfs(v,u); 16 for(int i=0;i<k;++i) 17 for(int j=0;j<k;++j){ 18 ll need=(k-(i+j+1)%k)%k;//when k-(i+j+1)%k==kor0 it need not add; 19 ans+=need*dp[u][i]*dp[v][j]; 20 } 21 for(int i=0;i<k;++i) 22 dp[u][(i+1)%k]+=dp[v][i]; 23 } 24 } 25 ans+=sum[u]*(n-sum[u]); 26 return sum[u]; 27 } 28 int main(void){ 29 std::ios::sync_with_stdio(false); 30 cin>>n>>k; 31 for(int i=1;i<n;++i){ 32 int u,v; 33 cin>>u>>v; 34 e[u].push_back(v); 35 e[v].push_back(u); 36 } 37 dfs(1,-1); 38 cout<<ans/k; 39 }优质内容筛选与推荐>>
1、从flexible.js引入高德地图谈起的移动端适配
2、C语言链表的简单实用
3、IOCP在网络应用中常见错误分析
4、Spark机器学习(11)：协同过滤算法
5、Cs Tip07: Sliding Doors of Cs(s)