fork download
copy 
  1. from sys import setrecursionlimit
  2.  
  3. setrecursionlimit(10**6)
  4.  
  5. class Graph:
  6.     def __init__(self,V):
  7.         self.V=V
  8.         self.graph=[[] for i in range(V+1)]
  9.         self.longest=1
  10.  
  11.     def addEdges(self):
  12.         for _ in range(len(self.graph)-2):
  13.             u,v=map(int, input().split())
  14.             self.graph[u].append(v)
  15.             self.graph[v].append(u)
  16.  
  17.         self.val=[0]
  18.         for i in input():
  19.             self.val.append(i)
  20.  
  21.     def DFS_BFS_mixed(self,qu,qu1,depth,alset):
  22.         self.longest = max(depth,self.longest)
  23.         set1=dict()
  24.         for each in qu1:
  25.             if self.val[each] in set1:
  26.                 set1[self.val[each]].append(each)
  27.             else:
  28.                 set1[self.val[each]]=[each]
  29.  
  30.         for each in qu:
  31.             if self.val[each] in set1:
  32.                 for every in set1[self.val[each]]:
  33.                     if (each not in alset) and (every not in alset):
  34.                         s1,s2 = set(self.graph[each]),set(self.graph[every])
  35.                         alset.add(each)
  36.                         alset.add(every)
  37.                         self.DFS_BFS_mixed(s1,s2,depth+2,alset)
  38.  
  39.     def start(self):
  40.         for i in range(1,self.V+1):
  41.             set1=dict()
  42.             for j in self.graph[i]:
  43.                 if self.val[i] == self.val[j]:
  44.                     s1,s2 = set(self.graph[i]),set(self.graph[j])
  45.                     path=set([i,j])
  46.                     self.DFS_BFS_mixed(s1,s2,2,path)
  47.                 if self.val[j] in set1:
  48.                     for each in set1[self.val[j]]:
  49.                         s1,s2 = set(self.graph[each]),set(self.graph[j])
  50.                         path=set([i,each,j])
  51.                         self.DFS_BFS_mixed(s1,s2,3,path)
  52.                     set1[self.val[j]].append(j)
  53.                 else:
  54.                     set1[self.val[j]]=[j]
  55.         print(self.longest)
  56.  
  57. t=int(input())
  58.  
  59. for _ in range(t):
  60.     V=int(input())
  61.     gra=Graph(V)
  62.     gra.addEdges()
  63.     gra.start()
  64.  
Success #stdin #stdout 0.02s 9364KB
comments (?)
stdin
copy 
1
3
1 2
2 3
mom
stdout
copy 
3
https://ideone.com/5DG9eX
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!