Submission #1043333

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=201000;
int dep[N],p[N][22];
int n,u,v,mc,md,pu,pv,maxd[N],mad[N],l[N],shav[N];
ll ret;
VI e[N];
char fav[N];
void dfs(int u,int f,int dis) {
	p[u][0]=f; dep[u]=dis;
	if (dis>md) md=dis,mc=u;
	for (auto v:e[u]) if (v!=f) {
		dfs(v,u,dis+1);
	}
}
#define LOGN 18
int lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,LOGN) if (dep[p[v][i]]>=dep[u]) v=p[v][i];
	if (u==v) return u;
	per(i,0,LOGN) if (p[v][i]!=p[u][i]) u=p[u][i],v=p[v][i];
	return p[u][0];
}
int dist(int u,int v) {
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void solve(int u,int f) {
	mad[u]=0;
	for (auto v:e[u]) if (v!=f) {
		solve(v,u);
		mad[u]=max(mad[u],mad[v]+1);
	}
	shav[u]=mad[u]+2; // if (u,d) d>=shav[u] -> (f,d-1)
	if (fav[u]=='1') l[u]=0;
//	printf("gg %d %d\n",u,maxd[u]);
	if (f!=0) {
		if (maxd[u]>maxd[f]) {
			l[f]=min(l[f],max(l[u]-1,shav[u]-1));
//			printf("ff %d %d %d\n",u,shav[u],l[u]);
			ret+=max(0,shav[u]-l[u]);
		} else {
			// double center
			shav[u]=maxd[u]; // d>=shav[u] -> (f,d)
			l[f]=min(l[f],max(l[u],shav[u]));
			ret+=max(0,shav[u]-l[u]);

		}
	} else ret+=max(0,maxd[u]-l[u]+1);
}
int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		scanf("%d%d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	dfs(1,0,1);
	md=0;
	pu=mc;
	dfs(pu,0,1);
	rep(j,1,LOGN) rep(i,1,n+1) p[i][j]=p[p[i][j-1]][j-1];
	pv=mc;
	rep(i,1,n+1) maxd[i]=max(dist(i,pu),dist(i,pv));
//	printf("ss %d %d\n",pu,pv);
//	rep(i,1,n+1) printf("%d ",maxd[i]); puts("");
	int rt=min_element(maxd+1,maxd+n+1)-maxd;
//	printf("root %d\n",rt);
	scanf("%s",fav+1);
	rep(i,1,n+1) l[i]=1<<30;
	solve(rt,0);
	printf("%lld\n",ret);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:74:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:76:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
                      ^
./Main.cpp:90:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",fav+1);
                   ^

Judge Result