문제
10ドル^{18}$개의 정점으로 이루어진 트리가 있습니다. 이 트리에는 2ドル \le i \le 10^{18}$인 $i$에 대해, $i$번째 정점과 $\left\lfloor \frac{i}{2} \right \rfloor$번째 정점을 잇는 간선이 있습니다.
이 트리에서 $K$개의 정점 $v_1, v_2, \cdots, v_K$가 주어집니다. 임의의 정점에서 시작해서 주어진 $K$개의 정점을 각각 한 번 이상 방문하는 경로 중, 가장 짧은 경로의 길이를 구하세요.
출력
각 테스트케이스마다 한 줄에 하나씩, 임의의 정점에서 시작해서 주어진 $K$개의 정점을 각각 한 번 이상 방문하는 경로 중, 가장 짧은 경로의 길이를 출력하세요.
노트
길이 $L$인 트리의 경로는 방문한 정점을 차례로 나열한 수열 $p_0, p_1, \cdots, p_L$로 표현되며, 1ドル \le i \le L$에 대해 $p_{i-1}$과 $p_i$가 서로 간선으로 연결되어 있어야 합니다. 같은 정점 혹은 간선을 여러 번 방문해도 됩니다.
W3sicHJvYmxlbV9pZCI6IjMwODExIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVFNQIiwiZGVzY3JpcHRpb24iOiI8cD4kMTBeezE4fSRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWM3NzQgXHVkMmI4XHViOWFjXHVjNWQwXHViMjk0ICQyIFxcbGUgaSBcXGxlIDEwXnsxOH0kXHVjNzc4ICRpJFx1YzVkMCBcdWIzMDBcdWQ1NzQsICRpJFx1YmM4OFx1YzlmOCBcdWM4MTVcdWM4MTBcdWFjZmMgJFxcbGVmdFxcbGZsb29yIFxcZnJhY3tpfXsyfSBcXHJpZ2h0IFxccmZsb29yJFx1YmM4OFx1YzlmOCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNzg3XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWQyYjhcdWI5YWNcdWM1ZDBcdWMxMWMgJEskXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMCAkdl8xLCB2XzIsIFxcY2RvdHMsIHZfSyRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWM3ODRcdWM3NThcdWM3NTggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgJEskXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWFjMDFcdWFjMDEgXHVkNTVjIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1YyBcdWM5MTEsIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggJFQkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgVCBcXGxlIDEwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWMyMTggJEskXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgyIFxcbGUgSyBcXGxlIDEwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzggJHZfMSwgdl8yLCBcXGNkb3RzLCB2X0skXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWJhYThcdWI0ZTAgJHZfaSRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk4NVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgdl9pIFxcbGUgMTBeezE4fSkkPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNzg1XHViODI1XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyAkSyRcdWM3NTggXHVkNTY5XHVjNzc0ICQxMDBcXCwwMDAkXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSwgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0ICRLJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVhYzAxXHVhYzAxIFx1ZDU1YyBcdWJjODggXHVjNzc0XHVjMGMxIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWMgXHVjOTExLCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWFlMzhcdWM3NzQgJEwkXHVjNzc4IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjYmRcdWI4NWNcdWIyOTQgXHViYzI5XHViYjM4XHVkNTVjIFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWNjMjhcdWI4NDBcdWI4NWMgXHViMDk4XHVjNWY0XHVkNTVjIFx1YzIxOFx1YzVmNCAkcF8wLCBwXzEsIFxcY2RvdHMsIHBfTCRcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHViYTcwLCAkMSBcXGxlIGkgXFxsZSBMJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJHBfe2ktMX0kXHVhY2ZjICRwX2kkXHVhYzAwIFx1YzExY1x1Yjg1YyBcdWFjMDRcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWM4MTAgXHVkNjM5XHVjNzQwIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YmMyOVx1YmIzOFx1ZDU3NFx1YjNjNCBcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDgxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRTUCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgYSB0cmVlIHdpdGggJDEwXnsxOH0kIG5vZGVzLiBGb3IgYWxsICRpJCBzdWNoIHRoYXQgJDIgXFxsZSBpIFxcbGUgMTBeezE4fSQsIHRoZXJlIGlzIGFuIGVkZ2UgY29ubmVjdGluZyBub2RlICRpJCBhbmQgbm9kZSAkXFxsZWZ0XFxsZmxvb3IgXFxmcmFje2l9ezJ9IFxccmlnaHQgXFxyZmxvb3IkIGluIHRoaXMgdHJlZS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiAkSyQgbm9kZXMsICR2XzEsIHZfMiwgXFxjZG90cywgdl9LJC4gRmluZCB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCB0cmFpbCB0aGF0IHZpc2l0cyBhbGwgJEskIG5vZGVzIGF0IGxlYXN0IG9uY2UgZnJvbSBhbiBhcmJpdHJhcnkgc3RhcnRpbmcgbm9kZSBpbiB0aGUgdHJlZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICRUJCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiAkKDEgXFxsZSBUIFxcbGUgMTBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBmb3IgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgJEskLCB0aGUgbnVtYmVyIG9mIGdpdmVuIG5vZGVzLiAkKDIgXFxsZSBLIFxcbGUgMTAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGZvciBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0aGUgbm9kZSBudW1iZXJzICR2XzEsIHZfMiwgXFxjZG90cywgdl9LJCwgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gQWxsIHZhbHVlcyBvZiAkdl9pJCBhcmUgdW5pcXVlLiAkKDEgXFxsZSB2X2kgXFxsZSAxMF57MTh9KSQ8XC9wPlxyXG5cclxuPHA+QWxsIHZhbHVlcyBnaXZlbiBpbiB0aGUgaW5wdXQgYXJlIGludGVnZXJzLjxcL3A+XHJcblxyXG48cD5UaGUgc3VtIG9mIGFsbCB2YWx1ZXMgb2YgJEskIGFjcm9zcyBhbGwgdGVzdCBjYXNlcyBkb2VzIG5vdCBleGNlZWQgJDEwMFxcLDAwMCQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgdHJhaWwgdGhhdCB2aXNpdHMgYWxsICRLJCBub2RlcyBhdCBsZWFzdCBvbmNlIGZyb20gYW4gYXJiaXRyYXJ5IHN0YXJ0aW5nIG5vZGUgaW4gYSBzaW5nbGUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IjxwPkEgdHJhaWwgb2YgbGVuZ3RoICRMJCBpbiBhIHRyZWUgaXMgcmVwcmVzZW50ZWQgYXMgdGhlIHNlcXVlbmNlIG9mIG5vZGVzIHZpc2l0ZWQsICRwXzAsIHBfMSwgXFxjZG90cywgcF9MJCwgYXJyYW5nZWQgaW4gb3JkZXIgb2YgdmlzaXQuIEZvciAkMSBcXGxlIGkgXFxsZSBMJCwgJHBfe2ktMX0kIGFuZCAkcF9pJCBtdXN0IGJlIGNvbm5lY3RlZC4gVGhlIHNhbWUgbm9kZSBvciBlZGdlIG1heSBiZSB2aXNpdGVkIG11bHRpcGxlIHRpbWVzLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==