vis10326's blog

By vis10326, 6 years ago, In English,

I am learning link cut tree. Can anyone please provide me some questions to solve related to link cut tree in increasing order of difficulty?

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

»
6 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Some not so trivial and practical:

  • Timus 1553. Caves and Tunnels

  • SPOJ 4155. OTOCI

  • liveArchive 5884. Strange Regulations

  • Codeforces 117E. Tree or not Tree

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks to both of you....

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

uva 11998 Rujia Liu loves Wario Land!

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=66&page=show_problem&problem=3149

I only solved it by ((n+m)*log(n))^1.5 using sqare_list to split and link heavy edges. I don't if there if there is lower time complexity appraoch.