The Story of a Tree
The Story of a Tree
+ 0 comments Python 3:
def dfs(v, adj_list, parent): for u in adj_list[v]: if u != parent[v]: parent[u] = v dfs(u, adj_list, parent) def sum_dfs(v, p, adj_list, count, k): count[v] += int(p != -1) * count[p] out = count[v] >= k for u in adj_list[v]: if u != p: out += sum_dfs(u, v, adj_list, count, k) return out def storyOfATree(n, edges, k, guesses): adj_list = {i:set() for i in range(n)} for u, v in edges: adj_list[u-1].add(v-1) adj_list[v-1].add(u-1) parent, count = [0]*n, [0]*n dfs(0, adj_list, parent) for u, v in guesses: if parent[v-1] == u-1: count[0] += 1 count[v-1] -= 1 else: count[u-1] += 1 n_correct = sum_dfs(0, -1, adj_list, count, k) out = Fraction(n_correct, n) return f"{out.numerator}/{out.denominator}"
+ 0 comments Python 3: dono what's wrong with my code orz~~
def storyOfATree(n, edges, k, guesses): cnn=[[] for _ in range(n+1)] for p,q in edges: cnn[p].append(q) cnn[q].append(p) win1=0 vist=[0]*(n+1) cur=[1] while cur: st=cur[0] del cur[0] if not vist[st]: vist[st]=1 for ed in cnn[st]: if not vist[ed]: win1+=[st,ed] in guesses cur.append(ed) vist=[-1]*(n+1); vist[0]=0 cur=[(1,win1)] while cur: st,win=cur[0] del cur[0] if vist[st]==-1: vist[st]=win for ed in cnn[st]: if vist[ed]==-1: cur.append((ed,win+([ed,st] in guesses)-([st,ed] in guesses))) wincount=sum([1 for x in vist if x>=k]) return '{}/{}'.format(wincount//(math.gcd(wincount,n)),n//(math.gcd(wincount,n)))
+ 0 comments I found this tough to implement, since a recursive dfs can easily overflow the stack for trees as large as 10^5 nodes..
+ 0 comments For all java versions the loop in main() which iterates over "g" iterates over "q" instead.
+ 1 comment Don't try to fill the given function, clean the editor and start from scratch , I thought my code has problem and started debugging but the given input to the function is wrong It took me 3 hours to figure it out , to know that value of 'g' is wrong i.e guesses.size().
Hint: If you have any doubt just think it as dfs and parent marking if you can't figure it how this is my code See only when you think you have tried hard. Another Hint: Take 1 as node draw a directed graph and try code
int gcd(int a,int b) { if(a==0) { return a; } else if(b==0) { return a; } else { return gcd(b,a%b); } } void dfs(int i,int pa,vector<int> adj[],vector<int> &par,vector<bool> &vis,vector<int> guess[],int &ans) { par[i] = pa; vis[i] = 1; for(auto a:adj[i]) { if(!vis[a]) { for(auto b:guess[i]) { if(b==a) { ans++; break; } } dfs(a,i,adj,par,vis,guess,ans); } } } void s_dfs(int i,vector<int> adj[],vector<int> &par,vector<bool> &vis,vector<int> guess[],int ans,int &root_count,int k) { vis[i] = 1; int c; for(auto a:adj[i]) { if(!vis[a]) { c = ans; for(auto b:guess[i]) { if(b==a) { ans--; break; } } par[i] = a; par[a] = 0; for(auto c:guess[a]) { if(c==i) { ans++; break; } } if(ans>=k) { root_count++; } s_dfs(a,adj,par,vis,guess,ans,root_count,k); ans = c; par[i] = 0; par[a] = i; } } } string storyOfATree(int n, vector<int> adj[], int k, vector<int> guess[],int g) { vector<bool> vis(n+1,0); vector<int> par(n+1,0); int ans = 0; int root_count = 0; dfs(1,0,adj,par,vis,guess,ans); if(ans>=k) { root_count++; } vector<bool> vvis(n+1,0); s_dfs(1,adj,par,vvis,guess,ans,root_count,k); string s=""; int a = gcd(root_count,n); if(a==0) { a=1; n = 1; } root_count = root_count/a; s += to_string(root_count); s += '/'; n = n/a; s += to_string(n); return s; } int main() { int T; cin >> T; while(T--) { int n; cin >> n; vector<int> adj[n+1]; int x,y; for(int i=1;i<n;i++) { cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } int g,k; cin >> g >> k; vector<int> guesses[n+1]; for(int i=0;i<g;i++) { cin >> x >> y; guesses[x].push_back(y); } cout << storyOfATree(n, adj,k,guesses,g) << "\n"; } return 0; }
changing the directions while traversing dfs and changing parents. code:
Sort 59 Discussions, By:
Please Login in order to post a comment