E. Tree Folding time limit per test2 seconds memory limit per test512 megabytes inputstandard input outputstandard output Vanya wants to minimize a tree. He can perform the following Operation multiple times: choose a vertex v, and two disjoint (except for v) paths of equal length a0?=?v, a1, …, ak, and b0?=?v, b1, …, bk. Additionally, vertices a1, …, ak, b1, …, bk must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices b1, …, bk can be effectively erased:
Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.
Input The first line of input contains the number of vertices n (2?≤?n?≤?2·105).
Next n?-?1 lines describe edges of the tree. Each of these lines contains two space-separated integers u and v (1?≤?u,?v?≤?n, u?≠?v) — indices of endpoints of the corresponding edge. It is guaranteed that the given graph is a tree.
Output If it is impossible to obtain a path, PRint -1. Otherwise, print the minimum number of edges in a possible path.
Examples input 6 1 2 2 3 2 4 4 5 1 6 output 3 input 7 1 2 1 3 3 4 1 5 5 6 6 7 output -1 Note In the first sample case, a path of three edges is obtained after merging paths 2?-?1?-?6 and 2?-?4?-?5.
It is impossible to perform any operation in the second sample case. For example, it is impossible to merge paths 1?-?3?-?4 and 1?-?5?-?6, since vertex 6 additionally has a neighbour 7 that is not present in the corresponding path.
題意：給你一棵樹，如果從一個(gè)頂點(diǎn)開始存在兩條到達(dá)葉節(jié)點(diǎn)的路徑，并且這兩條路徑的長(zhǎng)度相等，且每條路徑上除了這個(gè)頂點(diǎn)外其它的定點(diǎn)與非該路徑的的頂點(diǎn)沒有邊相連，那么我們可以執(zhí)行一種操作，這個(gè)操作是把這兩條路徑合并成一條路徑，也就是吧兩條路徑中的其中一條路徑刪除掉，問經(jīng)過若干次這種操作之后，這棵樹能不能變成一條路徑，如果能，輸出所有可能的路徑中最短的那個(gè)路徑的長(zhǎng)度，如果不能，則輸出-1.
解題思路： 我們分析題意可以得出，如果存在，則最后只有一種答案，因?yàn)橹灰獫M足執(zhí)行操作的條件，就必須刪除其中一條邊，不刪除的話，最后不可能得到單一路徑，而兩條邊是等價(jià)的，所以刪除哪條邊對(duì)最后的結(jié)果沒有影響，所以題目中那個(gè)讓你找出最短的邊是故意誤導(dǎo)你，所以不用管它，只需要判斷是否存在，判斷的方法是從每個(gè)葉節(jié)點(diǎn)開始bfs，邊刪除節(jié)點(diǎn)邊記錄每個(gè)頂點(diǎn)能夠到達(dá)的葉節(jié)點(diǎn)的長(zhǎng)度，如果最后有某個(gè)頂點(diǎn)到達(dá)的葉節(jié)點(diǎn)的長(zhǎng)度有三種或以上，則不存在解。特別需要注意的是儲(chǔ)存這棵樹時(shí)要用set來儲(chǔ)存，因?yàn)樵赽fs過程中需要不斷的刪除邊，所以用set比較方便，另外，用set的話會(huì)把重復(fù)的距離給自動(dòng)屏蔽掉，便于我們判斷。
#include<bits/stdc++.h>using namespace std;const int maxn = 2e5 + 10;int n;set<int> Edge[maxn];//保存每個(gè)定點(diǎn)相連的頂點(diǎn)set<int> Dis[maxn];//保存每個(gè)頂點(diǎn)與之能夠到達(dá)的葉節(jié)點(diǎn)的距離queue<int> Q;bool visit[maxn];int cal(int len){ while(len%2 == 0) { len /= 2; } return len;}int bfs(){ memset(visit,false,sizeof(visit)); while(!Q.empty()) { int u = Q.front(); Q.pop(); if(visit[u]) continue; if(Edge[u].size() == 1)//頂點(diǎn)u是葉節(jié)點(diǎn) { if(Dis[u].size() == 1)//只有一個(gè)能夠到達(dá)的葉節(jié)點(diǎn) { int v = *Edge[u].begin(); Edge[u].erase(v); Edge[v].erase(u); Q.push(v); Dis[v].insert(*Dis[u].begin() + 1); visit[u] = true; } } else if(Edge[u].size() == 0)//刪除的就剩最后一個(gè)頂點(diǎn) { if(Dis[u].size() >= 3)//無法形成單一路徑 { return -1; } else if(Dis[u].size() == 1) { return cal(*Dis[u].begin()); } else if(Dis[u].size() == 2) { return cal(*Dis[u].begin() + *(++Dis[u].begin())); } } } return -1;}int main(){ scanf("%d",&n); int u,v; while(!Q.empty()) Q.pop(); for(int i = 1; i <= n - 1; i++) { scanf("%d%d",&u,&v); Edge[u].insert(v); Edge[v].insert(u); } for(int i = 1; i <= n; i++) { if(Edge[i].size() == 1) { Q.push(i);//將所有葉節(jié)點(diǎn)加入隊(duì)列 Dis[i].insert(0);//初始化，為bfs做準(zhǔn)備 } } printf("%d/n",bfs()); return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
