tree/diameterforvertex.cpp

• View this file on GitHub
• Last update: 2020-09-30 16:50:39+09:00
• Link: https://atcoder.jp/contests/arc097/tasks/arc097_d

Verified with

• test/aoj/0415.test.cpp

Code

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct DiameterForVertex{
  vector<T> vs,dp;
  vector<vector<int> > G;
  DiameterForVertex(int n):dp(n),G(n){}
  DiameterForVertex(vector<T> vs):vs(vs),dp(vs.size()),G(vs.size()){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int &s){
    if(p<0) dp[v]=T(0);
    dp[v]+=vs[v];
    if(dp[s]<dp[v]) s=v;
    for(int u:G[v]){
      if(u==p) continue;
      dp[u]=dp[v];
      dfs(u,v,s);
    }
  }

  T build(){
    assert(!vs.empty());
    int s=0;
    dfs(s,-1,s);
    dfs(s,-1,s);
    return dp[s];
  }

  T build(vector<T> us){
    assert(us.size()==dp.size());
    vs=us;
    return build();
  }
};
//END CUT HERE
#ifndef call_from_test

// test build with argument vector<T>
signed ARC097_F(){
  int n;
  cin>>n;
  DiameterForVertex<int> G(n);
  vector<int> deg(n,0);
  for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G.add_edge(x,y);
    deg[x]++;
    deg[y]++;
  }

  string s;
  cin>>s;

  int cnt=(n-1)*2,num=0;
  queue<int> que;
  vector<int> dead(n,0);
  for(int i=0;i<n;i++){
    num+=(s[i]=='W');
    if((deg[i]==1) and (s[i]=='B')){
      dead[i]=1;
      que.emplace(i);
    }
  }

  while(!que.empty()){
    int v=que.front();que.pop();
    cnt-=2;
    for(int u:G.G[v]){
      if(dead[u]) continue;
      deg[u]--;
      if(deg[u]==1 and (s[u]=='B')){
        dead[u]=1;
        que.emplace(u);
      }
    }
  }

  if(num<=1){
    cout<<num<<endl;
    return 0;
  }

  vector<int> vs(n,0);
  for(int i=0;i<n;i++){
    if(dead[i]) continue;
    vs[i]=deg[i]+(s[i]=='W');
    vs[i]%=2;
    cnt+=vs[i];
  }

  cout<<cnt-G.build(vs)*2<<endl;
  return 0;
}
/*
  verified on 2019/12/27
  https://atcoder.jp/contests/arc097/tasks/arc097_d
*/

signed main(){
  //ARC097_F();
  return 0;
}
#endif

#line 1 "tree/diameterforvertex.cpp"

#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct DiameterForVertex{
  vector<T> vs,dp;
  vector<vector<int> > G;
  DiameterForVertex(int n):dp(n),G(n){}
  DiameterForVertex(vector<T> vs):vs(vs),dp(vs.size()),G(vs.size()){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int &s){
    if(p<0) dp[v]=T(0);
    dp[v]+=vs[v];
    if(dp[s]<dp[v]) s=v;
    for(int u:G[v]){
      if(u==p) continue;
      dp[u]=dp[v];
      dfs(u,v,s);
    }
  }

  T build(){
    assert(!vs.empty());
    int s=0;
    dfs(s,-1,s);
    dfs(s,-1,s);
    return dp[s];
  }

  T build(vector<T> us){
    assert(us.size()==dp.size());
    vs=us;
    return build();
  }
};
//END CUT HERE
#ifndef call_from_test

// test build with argument vector<T>
signed ARC097_F(){
  int n;
  cin>>n;
  DiameterForVertex<int> G(n);
  vector<int> deg(n,0);
  for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G.add_edge(x,y);
    deg[x]++;
    deg[y]++;
  }

  string s;
  cin>>s;

  int cnt=(n-1)*2,num=0;
  queue<int> que;
  vector<int> dead(n,0);
  for(int i=0;i<n;i++){
    num+=(s[i]=='W');
    if((deg[i]==1) and (s[i]=='B')){
      dead[i]=1;
      que.emplace(i);
    }
  }

  while(!que.empty()){
    int v=que.front();que.pop();
    cnt-=2;
    for(int u:G.G[v]){
      if(dead[u]) continue;
      deg[u]--;
      if(deg[u]==1 and (s[u]=='B')){
        dead[u]=1;
        que.emplace(u);
      }
    }
  }

  if(num<=1){
    cout<<num<<endl;
    return 0;
  }

  vector<int> vs(n,0);
  for(int i=0;i<n;i++){
    if(dead[i]) continue;
    vs[i]=deg[i]+(s[i]=='W');
    vs[i]%=2;
    cnt+=vs[i];
  }

  cout<<cnt-G.build(vs)*2<<endl;
  return 0;
}
/*
  verified on 2019/12/27
  https://atcoder.jp/contests/arc097/tasks/arc097_d
*/

signed main(){
  //ARC097_F();
  return 0;
}
#endif

Back to top page