Last contest,I failed system test on D,that I didn't become an IGM.↵
↵
But I don't know why my D failed system test,I submitted the same code $3$ times today,they all get Accepted.See [submission:72380842] [submission:72380904] [submission:72381047]↵
↵
I think it's the problem of randomized integers,but I don't know why.Please help me!↵
↵
Here's my solution to D:↵
Let's Maintain candidate roots,at the beginning,every vertex is a candidate root.In each query,we randomly choose two candidate roots that are not adjacent ans not equal.Let's denote them $x$,$y$,then we ask $x$,$y$'s lca,denote it $w$,then for every $w$'s subtree that contains $x$ or $y$,all of the vertex in it can be removed from candidate root.It can be shown that in each query,we remove at least two candidate roots.All the vertices left form a subtree of the original tree.There's a special case on $n=2$,just ask these two vertices.↵
↵
Here's my submission:[submission:72324004]↵
↵
Sorry for my poor English.↵
↵
But I don't know why my D failed system test,I submitted the same code $3$ times today,they all get Accepted.See [submission:72380842] [submission:72380904] [submission:72381047]↵
↵
I think it's the problem of randomized integers,but I don't know why.Please help me!↵
↵
Here's my solution to D:↵
Let's Maintain candidate roots,at the beginning,every vertex is a candidate root.In each query,we randomly choose two candidate roots that are not adjacent ans not equal.Let's denote them $x$,$y$,then we ask $x$,$y$'s lca,denote it $w$,then for every $w$'s subtree that contains $x$ or $y$,all of the vertex in it can be removed from candidate root.It can be shown that in each query,we remove at least two candidate roots.All the vertices left form a subtree of the original tree.There's a special case on $n=2$,just ask these two vertices.↵
↵
Here's my submission:[submission:72324004]↵
↵
Sorry for my poor English.↵