Submission #1071722

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define foreach( gg,itit )  for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define mp make_pair
#define pb push_back
#define all(s) s.begin(),s.end()
#define present(c,x) ((c).find(x) != (c).end())
const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF = 1e18;

//#define DEBUG
ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}
#ifdef DEBUG
#define dprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#else
#define dprintf(fmt,...)
#endif

vector<int> G[N];
char s[N];
int mx[N],sub[N],mn[N],lw[N];
void dfs(int v,int p){
  sub[v]=0;
  if(s[v]=='1') lw[v]=1;
  REP(i,G[v].size()) if(G[v][i]!=p) {
    dfs(G[v][i],v);
    lw[v]|=lw[G[v][i]];
    sub[v]=max(sub[v],sub[G[v][i]]+1);
  } 
}
void dfs1(int v,int p,int l,int ik){
  pii arr[2]; FILL(arr,0);
  mn[v]=mod;
  if(ik) mn[v]=l;
  arr[0]=mp(l,p);

  REP(i,G[v].size()) if(G[v][i]!=p) {
    pii z = mp(sub[G[v][i]]+1,G[v][i]);
    if(lw[G[v][i]]) mn[v]=min(mn[v],sub[G[v][i]]+1);
    ik+=lw[G[v][i]];
    if(z>arr[0]) arr[1]=arr[0],arr[0]=z;
    else arr[1]=max(arr[1],z);
  }
  if(s[v]=='1') mn[v]=0,ik++;
  mx[v]=min(arr[0].X-1,arr[1].X+1);
 // printf("%d %d\n",v+1,mx[v]+1);
  REP(i,G[v].size()) if(G[v][i]!=p){
    int p = (ik>lw[G[v][i]]);
    if(G[v][i]!=arr[0].Y) dfs1(G[v][i],v,arr[0].X+1,p);
    else dfs1(G[v][i],v,arr[1].X+1,p);
  }
}
int main(){
  int n; scanf("%d",&n);
  REP(i,n-1){
    int x,y; scanf("%d%d",&x,&y); x--;y--;
    G[x].pb(y); G[y].pb(x);
  }
  scanf("%s",s);
  dfs(0,-1);
  dfs1(0,-1,0,0);
  ll ans=1;
  REP(i,n) if(mn[i]<=mx[i]) ans+=mx[i]-mn[i]+1;
  printf("%lld\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:72:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int n; scanf("%d",&n);
                        ^
./Main.cpp:74:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int x,y; scanf("%d%d",&x,&y); x--;y--;
                                 ^
./Main.cpp:77:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
                ^

Judge Result