Submission #1414845

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 114514
int n;
vector<int> G[MAX],nG[MAX],rG[MAX];
int ans;
int dp[2][MAX];
map<int,int> cnt1[MAX],cnt2[MAX];
int dfs1(int v,int p){
  int res=0;
  for(int u:G[v]){
    if(u==p) continue;
    int tmp=dfs1(u,v);
    res=max(res,tmp);
    cnt1[v][tmp]++;
  }
  for(int u:nG[v]){
    if(u==p) continue;
    int tmp=dfs1(u,v);
    res=max(res,tmp);
    cnt1[v][tmp]++;
  }

  for(int u:rG[v]){
    if(u==p) continue;
    dfs1(u,v);
  }
  
  ans=max(ans,res-1);

  //cout<<v<<":"<<endl;for(auto p:cnt1[v]) cout<<p.first<<":"<<p.second<<endl;cout<<endl;
  
  return dp[0][v]=res+1;
}
int dfs2(int v,int p){
  int res=0;
  for(int u:G[v]){
    if(u==p) continue;
    int tmp=dfs2(u,v);
    res=max(res,tmp);
    cnt2[v][tmp]++;
  }
  for(int u:rG[v]){
    if(u==p) continue;
    int tmp=dfs2(u,v);
    res=max(res,tmp);
    cnt2[v][tmp]++;
  }
  
  for(int u:nG[v]){
    if(u==p) continue;
    dfs2(u,v);
  }
  
  ans=max(ans,res-1);
  
  //cout<<v<<";"<<endl;for(auto p:cnt2[v]) cout<<p.first<<";"<<p.second<<endl;cout<<endl;
  
  return dp[1][v]=res+1;
}
void dfs3(int v,int p){
  for(int u:G[v]){
    if(u==p) continue;
    dfs3(u,v);
  }
  for(int u:nG[v]){
    if(u==p) continue;
    dfs3(u,v);
  }
  for(int u:rG[v]){
    if(u==p) continue;
    dfs3(u,v);
  }
  for(int u:G[v]){
    if(u==p) continue;
    int k=dp[0][u],l=dp[1][u];
    cnt1[v][k]--;
    cnt2[v][l]--;
    //cout<<v<<" "<<u<<":"<<k<<" "<<l<<endl;
    if(cnt1[v][k]==0) cnt1[v].erase(cnt1[v].find(k));
    if(cnt2[v][l]==0) cnt2[v].erase(cnt2[v].find(l));
    if(!cnt1[v].empty()){
      int x=(--cnt1[v].end())->first;
      ans=max(ans,l+x-1);
    }
    if(!cnt2[v].empty()){
      int y=(--cnt2[v].end())->first;
      ans=max(ans,k+y-1);
    }
    cnt1[v][k]++;
    cnt2[v][l]++;
  }
  for(int u:nG[v]){
    if(u==p) continue;
    int k=dp[0][u];
    //cout<<v<<" "<<u<<":"<<k<<endl;
    cnt1[v][k]--;
    if(cnt1[v][k]==0) cnt1[v].erase(cnt1[v].find(k));
    if(!cnt2[v].empty()){
      int y=(--cnt2[v].end())->first;
      ans=max(ans,k+y-1);
    }
    cnt1[v][k]++;
  }
  for(int u:rG[v]){
    if(u==p) continue;
    int l=dp[1][u];
    //cout<<v<<" "<<u<<";"<<l<<endl;
    cnt2[v][l]--;
    if(cnt2[v][l]==0) cnt2[v].erase(cnt2[v].find(l));
    if(!cnt1[v].empty()){
      int x=(--cnt1[v].end())->first;
      ans=max(ans,l+x-1);
    }
    cnt2[v][l]++;
  }
}
signed main(){
  cin>>n;
  for(int i=0;i<n-1;i++){
    int a,b,t;
    cin>>a>>b>>t;
    a--;b--;
    if(t==1){
      nG[a].push_back(b);
      rG[b].push_back(a);
    }else{
      G[a].push_back(b);
      G[b].push_back(a);
    }
  }
  ans=0;
  memset(dp,0,sizeof(dp));
  dfs1(0,-1);
  dfs2(0,-1);
  //for(int i=0;i<n;i++) cout<<i<<":"<<dp[0][i]<<" "<<dp[1][i]<<endl;
  
  dfs3(0,-1);
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result