Submission #38725889

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
template<typename T> void chkmn(T &a, const T &b)
{
	(a > b) && (a = b);
}
template<typename T> void chkmx(T &a, const T &b)
{
	(a < b) && (a = b);
}
int inc(const int &a, const int &b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}
int dec(const int &a, const int &b)
{
	return a - b < 0 ? a - b + MOD : a - b;
}
int mul(const int &a, const int &b)
{
	return 1LL * a * b % MOD;
}
void Inc(int &a, const int &b)
{
	((a += b) >= MOD) && (a -= MOD);
}
void Dec(int &a, const int &b)
{
	((a -= b) < 0) && (a += MOD);
}
const int N = 2e5 + 5;
struct Lexington
{
	int e, ne;
};
struct Sakawa
{
	int idx, h[N];
	Lexington lxt[2 * N];
	void add(int a, int b)
	{
		lxt[++idx] = (Lexington){b, h[a]};
		h[a] = idx;
	}
	void adds(int a, int b)
	{
		add(a, b), add(b, a);
	}
	int depth[N];
	void dfs(int u, int fa)
	{
		depth[u] = depth[fa] + 1;
		for(int i = h[u]; i; i = lxt[i].ne)
		{
			int v = lxt[i].e;
			if(v == fa) continue;
			dfs(v, u);
		}
	}
}skw;
int n, qwq[N], ans;
int ds[N], dt[N];
int d, D, cnt[N];
int main()
{
	scanf("%d", &n);
	qwq[0] = 1;
	for(int i = 1; i <= n; ++i)
		qwq[i] = mul(qwq[i - 1], 2);
	for(int i = 1; i < n; ++i)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		skw.adds(a, b);
	}
	skw.dfs(1, 0);
	int S = 1;
	for(int i = 1; i <= n; ++i)
		if(skw.depth[i] > skw.depth[S])
			S = i;
	skw.dfs(S, 0);
	int T = 1;
	for(int i = 1; i <= n; ++i)
	{
		ds[i] = skw.depth[i] - 1;
		if(ds[i] > ds[T]) T = i;
	}
	skw.dfs(T, 0);
	D = skw.depth[S] - 1;
	for(int i = 1; i <= n; ++i)
	{
		dt[i] = skw.depth[i] - 1;
		chkmx(d, min(ds[i], dt[i]));
		cnt[max(ds[i], dt[i])]++;
	}
	for(int i = 1; i <= n; ++i)
		cnt[i] += cnt[i - 1];
	for(int i = 0; i < d; ++i)
		Inc(ans, qwq[n]);
	for(int i = d; i < D; ++i)
		Inc(ans, dec(qwq[n], qwq[cnt[i] + 1]));
	printf("%d\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:68:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:75:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   75 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Judge Result