Submission #1414868

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;


vector<int> e[2][100000];


int mem[2][100000];

int dfs(int p,int f,int pr){
int res=0;
 
  if(f==-1){
    int a=0,b=0;
    for(int i=0;i<e[0][p].size();i++)a=max(a,dfs(e[0][p][i] , 0,p) );
    for(int i=0;i<e[1][p].size();i++)b=max(b,dfs(e[1][p][i] , 1,p) );
    return max(a,b);
  }
  else {

    
    if(mem[f][p]!=-1)return mem[f][p];

    for(int i=0;i<e[f][p].size();i++)
      if(e[f][p][i]!=pr)
	res=max(res,dfs(e[f][p][i],f,p));

  }
  return mem[f][p]=res+1;

}

int main(){
  int n;
  int a,b,t;
  cin>>n;
  for(int i=0;i<n-1;i++){
    cin>>a>>b>>t;
    a--,b--;
    e[0][a].push_back(b);
    e[1][b].push_back(a);
    
    if(t==2) {
      e[0][b].push_back(a);
      e[1][a].push_back(b);
    }
    
  }
  memset(mem,-1,sizeof(mem));
  
  int ans=0;

  for(int i=0;i<n;i++){
    if(e[0][i].size()==1||e[1][i].size()==1)
      ans=max(ans,dfs(i,-1,-1));
  }

  cout<<ans-1<<endl;
  
  return 0;
}

Submission Info

Judge Result