牛牛一开始在1号房间。牛妹在某个另外的房间。牛牛想去寻找牛妹,但是他没有地图,所以只能在房间之间乱走。
牛牛每走过一条通道需要花费1金币,每条通道最多只能走两次。
牛牛有一个乱走规则:如果当前牛牛有 没走过的通道 可以走,牛牛就不会去走 走过一次的通道
这个规则可以保证只要钱足够就一定可以找到牛妹。
有m个查询,每次询问如果牛妹在号房间,请问牛牛身上至少要带多少金币才可以保证任何情况下都可以找到牛妹。
4,1,[1,2,2],[2,3,4],[3]
[4]
花费金币最多的方案是1->2->4->2->3
第一个参数n代表房间数量
第二个参数m代表查询数量
第三、四个参数vector u,v代表通道,与通过通道相连
第五个参数vector x代表m次查询中牛妹的位置
class Solution { public: /** * 寻找牛妹 * @param n int整型 * @param m int整型 * @param u int整型vector * @param v int整型vector * @param x int整型vector * @return int整型vector */ vector<int> G[200003]; int d[200003], f[200003]; int DFS(int u, int p, int k){ int cnt = 0; for(auto &x: G[u]){ if(x == p) continue; cnt += DFS(x, u, k+1); } f[u] = cnt; d[u] = k; return cnt+1; } vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) { vector<int> r; memset(d, 0, sizeof(d)); memset(f, 0, sizeof(f)); for(int i=0;i<n-1;i++){ G[u[i]].push_back(v[i]); G[v[i]].push_back(u[i]); } DFS(1, -1, 0); for(auto &t: x) r.push_back(d[t] + 2*(n-1-d[t]-f[t])); return r; } };
int dfs(vector<vector<int>> &graph,vector<int> &subNodes,vector<int> &height,int k,int cur,int pre){ int count = 0; for(int i=0;i<graph[cur].size();i++){ if(graph[cur][i] == pre){ continue; } count += dfs(graph,subNodes,height,k+1,graph[cur][i],cur); } subNodes[cur] = count; height[cur] = k; return count+1; } vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) { vector<vector<int>> graph(n+1); for(int i=0;i<u.size();i++){ graph[u[i]].push_back(v[i]); graph[v[i]].push_back(u[i]); } vector<int> subNodes(n+1,0); vector<int> height(n+1,0); dfs(graph,subNodes,height,0,1,-1); vector<int> res; for(int i=0;i<m;i++){ int count = 1 * height[x[i]] + 2 * (n - 1 - height[x[i]] - subNodes[x[i]]); res.push_back(count); } return res; }