首页 > 代码库 > （树形dp+LCA倍增法）CSU 1915 - John and his farm
（树形dp+LCA倍增法）CSU 1915 - John and his farm
题意：
有一个棵树，现在让你找两个点连接起来，这样必然成为一个环，现在要求这些环长度的期望，也就是平均值。
分析：
第一次做LCA题，做多校的时候，瞎几把找了模板敲，敲了个八九不离十，只是姿势不太好，需要考虑很多细节。
其实我觉得这题最多只能算中等题。
因为一直没空，写题解也晚了，已经有很多人写了题解，都写的不错。反正比我厉害。
这题用倍增法比较好一些，因为会用到关键点，也就是当v和u处在同一棵子树中时，找到更高点的下面那个点，倍增法通过深度跳跃可以很快找到。处理起来比其他两个LCA算法都方便。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 #include <map> 7 #include <queue> 8 9 10 using namespace std; 11 12 const int inf = 0x3f3f3f3f; 13 const int maxn = 100010; 14 const int DEG = 20; 15 16 #define fi first 17 #define se second 18 19 typedef long long ll; 20 21 vector<int> g[maxn]; 22 23 int fa[maxn][DEG]; 24 int deg[maxn]; 25 26 int n, q; 27 int u, v; 28 29 void bfs(int root) { 30 queue<int> q; 31 deg[root] = 0; 32 fa[root][0] = root; 33 q.push(root); 34 while(!q.empty()) { 35 int tmp = q.front(); 36 q.pop(); 37 for(int i = 1; i < DEG; i++) { 38 fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; 39 } 40 for(int i = 0; i < g[tmp].size(); i++) { 41 int v = g[tmp][i]; 42 if(v == fa[tmp][0])continue; 43 deg[v] = deg[tmp] + 1; 44 fa[v][0] = tmp; 45 q.push(v); 46 } 47 } 48 } 49 50 int LCA(int u, int v) { 51 if(deg[u] > deg[v])swap(u, v); 52 for(int det = deg[v] - deg[u], i = 0; det; det >>= 1, i++) { 53 if(det & 1)v = fa[v][i]; 54 } 55 if(u == v)return u; 56 for(int i = DEG - 1; i >= 0; i--) { 57 if(fa[u][i] != fa[v][i]) { 58 u = fa[u][i]; 59 v = fa[v][i]; 60 } 61 } 62 return fa[u][0]; 63 } 64 65 int len[maxn][2]; 66 int son[maxn]; 67 68 void dfs1(int u, int pre) { 69 son[u] = 1; 70 for(int i = 0; i < g[u].size(); i++) { 71 int v = g[u][i]; 72 if(v == pre)continue; 73 dfs1(v, u); 74 son[u] += son[v]; 75 len[u][0] += len[v][0] + son[v]; 76 } 77 len[u][1] = len[u][0]; 78 } 79 80 void dfs2(int u, int pre) { 81 for(int i = 0; i < g[u].size(); i++) { 82 int v = g[u][i]; 83 if(v == pre)continue; 84 len[v][1] += (len[u][1] - len[v][0] - son[v] + n - son[v]); 85 dfs2(v, u); 86 } 87 } 88 89 int up(int x, int step) { 90 for(int i = 0; i < DEG; i++) { 91 if(step & (1 << i))x = fa[x][i]; 92 } 93 return x; 94 } 95 96 void init() { 97 memset(len, 0, sizeof(len)); 98 memset(son, 0, sizeof(son)); 99 for(int i = 0; i < maxn; i++)g[i].clear();100 }101 102 103 104 105 int main() {106 while(~scanf("%d%d", &n, &q)) {107 init();108 for(int i = 0; i < n - 1; i++) {109 scanf("%d%d", &u, &v);110 g[u].push_back(v);111 g[v].push_back(u);112 }113 bfs(1);114 dfs1(1, 1);115 dfs2(1, 1);116 117 while(q--) {118 scanf("%d%d", &u, &v);119 if(deg[u] < deg[v])swap(u, v);120 int f = LCA(u, v);121 int dis = deg[u] + deg[v] - deg[f] * 2;122 if(f == v) {123 int core = up(u, deg[u] - deg[v] - 1);124 ll sum = (ll)son[u] * (n - son[core]);125 ll tolen = (ll)len[u][0] * (n - son[core]) + (ll)(len[v][1] - len[core][0] - son[core]) * son[u] + (ll)dis * sum + sum;126 printf("%f\n", tolen * 1.0 / sum);127 } else {128 ll sum = (ll)son[v] * son[u];129 ll tolen = (ll)len[v][0] * son[u] + (ll)len[u][0] * son[v] + (ll)sum * dis + sum;130 printf("%f\n", tolen * 1.0 / sum);131 }132 133 134 }135 136 }137 return 0;138 139 }
（树形dp+LCA倍增法）CSU 1915 - John and his farm
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。