Some queries about modification on trees

Revision en2, by PengsenMao, 2017-08-09 12:07:50

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English PengsenMao 2017-08-09 12:07:50 8 Tiny change: '(1<<i)) p[i][j] = min(p[i][j], w), u =' -> '(1<<i)) p[u][i] = min(p[u][i], w), u ='
en1 English PengsenMao 2017-08-09 02:47:31 1197 Initial revision (published)