PengsenMao's blog

By PengsenMao, history, 6 years ago,

Hey guys, i was working on this problem 827D-Best edge weight

There is a skill i learnt from a code, if you used two-power walk (i don't know how to call it in a proper way), let fa[i][j] represents you start from i, walk 2j steps upward, the vertex you can reach. p[i][j] represents the same stuff but instead of storing the vertex you can reach, we store the minimum weight among all the edges you pass from u to v.

if you want to change the weights on all the edges on the path from u to v on the tree, you only need to do the following part:

void modify(int u,int z,int w) //change to w, assume z is the lca to (u,v) coz u can split it into u->lca,v->lca
{
int c = dep[u]-dep[z];
for(int i = 19; i >= 0; -- i) if(c&(1<<i)) p[u][i] = min(p[u][i], w), u = fa[u][i];
}


and then in the main function, we do

fd(j,19,1) fo(i,1,n)
{
p[j-1][i] = min(p[j-1][i], p[j][i]);
p[j-1][fa[j-1][i]] = min(p[j-1][fa[j-1][i]], p[j][i]);
}


i am wondering if this skill is correct and i can use it for any offline modification?

thanks :P

• +8

 » 6 years ago, # |   +5 In modify() in your code, j is not defined in the loop. I don't understand anything going on in the code, can you explain in English or give link to submission instead?
•  » » 6 years ago, # ^ |   0 updated, thanks for figuring it out
 » 6 years ago, # | ← Rev. 2 →   -10 I think it is called binary lifting.