PengsenMao's blog

By PengsenMao, history, 7 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

»
7 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

I think it is called binary lifting.