网站的例子,沈阳淘宝网站建设,建设银行官网网站首页,个人网站html模板下载题目
CF2033G
分析 一道很显然是树形dp的题#xff0c;但非常恶心QwQ。 先不管复杂度#xff0c;找找递推关系#xff0c;一种很直接的想法如下#xff08;我觉得是错误的#xff09;#xff1a; d p [ i ] [ k ] m a x ( d p [ f a i ] [ k − 1 ] , d p [ s o …题目
CF2033G
分析 一道很显然是树形dp的题但非常恶心QwQ。 先不管复杂度找找递推关系一种很直接的想法如下我觉得是错误的 d p [ i ] [ k ] m a x ( d p [ f a i ] [ k − 1 ] , d p [ s o n i , j [ k ] 1 ) dp[i][k] max(dp[fa_{i}][k-1], dp[son_{i,j}[k]1) dp[i][k]max(dp[fai][k−1],dp[soni,j[k]1) 其中 d p [ i ] [ k ] dp[i][k] dp[i][k]表示从 i i i开始能量为 k k k的最远距离 f a i fa_{i} fai表示 i i i的根节点 s o n i , j son_{i,j} soni,j表示 i i i的第 j j j个子节点 这样的问题是会计入这样的路线实际距离为2算成了4 所以我们得把向上和向下两种情况分开记录 d p 1 [ i ] dp1[i] dp1[i]表示向下最远距离由于向下不消耗能量所以可以少一维 d p 2 [ i ] [ i d ] dp2[i][id] dp2[i][id]表示 i i i节点如果删掉第 i d id id条边后向下最远距离注意空间限制 d p 2 dp2 dp2得用 v e c t o r vector vector存储 i d id id得另外先预处理好链式前向星可能会好一点 i d [ i ] id[i] id[i]表示边 ( i , f a i ) (i, fa_{i}) (i,fai)在 f a i fa_{i} fai的 v e c t o r vector vector中的下标 h [ i ] h[i] h[i]表示节点 i i i的深度根节点深度为 1 1 1 于是得到答案的式子为 A N S ( i , k ) m a x ( d p 1 [ i ] , d p 2 [ j ] [ i d f r o m i ] h [ i ] − h [ j ] ) ANS(i, k) max(dp1[i], dp2[j][id \ from \ \ i] h[i] - h[j]) ANS(i,k)max(dp1[i],dp2[j][id from i]h[i]−h[j]) 后面的部分看起来很复杂实际上直接用 S T ST ST表维护即可
代码
#includebits/stdc.h
#define N 200005
#define inf 1000000000
using namespace std;
int t, n, q, fa[N][21], h[N], dp1[N], st[N][21];
int id[N]; // 记录每个根边的id
vectorint G[N], dp2[N]; // 去掉边i后向下最远
void cl() {for(int j0;(1j) n;j) {for(int i1;in;i) {st[i][j] -inf;}}for(int i1;in;i) {id[i] 0;dp1[i] 0;}for(int i1;in;i) {vectorint().swap(G[i]);vectorint().swap(dp2[i]);}
}
void init(int x, int pre) {for(int j1;(1j) h[x];j) fa[x][j] fa[fa[x][j-1]][j-1];for(int i0;iG[x].size();i) {int y G[x][i];if(y pre) continue;id[y] i;h[y] h[x] 1;fa[y][0] x;init(y, x);}
}
void dfs(int x, int pre) {dp1[x] 0; // dp1是最大se是第二大int se -inf; for(int i0;iG[x].size();i) {int y G[x][i];if(y pre) continue;dfs(y, x);if(dp1[y] 1 dp1[x]) {se dp1[x];dp1[x] dp1[y] 1;} else if(dp1[y] 1 se) {se dp1[y] 1;}}for(int i0;iG[x].size();i) {int y G[x][i];if(y pre) {dp2[x].push_back(-inf);continue;}if(dp1[x] dp1[y] 1) dp2[x].push_back(se);else dp2[x].push_back(dp1[x]);}
}
void show() {coutshowingendl;coutid: ; for(int i1;in;i) coutid[i] ; coutendl;couth: ; for(int i1;in;i) couth[i] ; coutendl;coutdp1: ;for(int i1;in;i) coutdp1[i] ;coutendl;for(int i1;in;i) {for(int j0;jG[i].size();j) {if(G[i][j] fa[i][0]) continue;printf(root %d, erase %d, dp2: %d\n, i, G[i][j], dp2[i][j]);}}for(int j0;(1j) n; j) {for(int i1;in;i) {if((1j) h[i]) printf(st[%d][%d]: %d \n ,i, j, st[i][j]);}}coutendl;
}
int main() {cint;while(t--) {cinn;cl();for(int i1;in-1;i) {int u, v; scanf(%d %d, u, v);G[u].push_back(v);G[v].push_back(u);} h[1] 1; id[1] -1;init(1, 0);dfs(1, 0);for(int i2;in;i) st[i][0] dp2[fa[i][0]][id[i]] - h[fa[i][0]]; for(int j1;(1j) n;j) {for(int i1;in;i) {if((1j) h[i]) st[i][j] max(st[i][j-1], st[fa[i][j-1]][j-1]);}}// show();cinq;while(q--) {int v, k; scanf(%d %d, v, k);k min(k, h[v]-1);int ans dp1[v];int step log2(k), now v;for(int step0;(1step) k; step) {if(!(k (1step))) continue;ans max(ans, st[now][step] h[v]);now fa[now][step];}printf(%d , ans);}}
}
