~~首先是个人都能看出来本题正解时间复杂度是线性的~~

- $10\ pts$ ~ $30\ pts$ :

对每个点枚举两个点，计算合法路径的权值和即可

时间复杂度$O(n^4)$，可通过树上前缀和优化为$O(n^3)$

- $50\ pts$ :

通过对题目的观察可以知道，选取某个点 $u$ 时，树上的点可以被分为两类：与 $u$ 的距离为奇数的点和与 $u$ 的距离为偶数的点，分别对应题目中的 $s(u,x)=0$ 和 $s(u,x)=1$。

设奇数点与 $u$ 的距离总和为 $s_1$，偶数点与选取点距离总和为 $s_2$ 则对于 $u$，答案就是 $s_1\times s_2$。

对每个点进行一次dfs即可得到所有答案。

时间复杂度$O(n^2)$

- $100\ pts$

由于对每个点 $u$ 的答案为 $s_1\times s_2$, 考虑先以一个点为根求出该点的 $s_1$ 与 $s_2$，然后再进行一次dfs，对每个儿子修改 $s_1$ 和 $s_2$ （具体看代码），然后记录每个点的答案。

时间复杂度$O(n)$

~~考试的时候被取模卡没了10pts~~

AC代码：

```cpp
#include<bits/stdc++.h>
#define loop(x,l,r) for(ll (x) = (l);(x)<=(r);++(x))
#define elif else if
using namespace std;
using ll = __int128_t;
#define N 500005
#define MOD 720021013ll
vector<ll> e[N];
ll cnt[2],n;
ll scnt[N][2];
ll typ[N],ct[N];
ll ans[N];
void dfs(ll u,ll fa,ll flag,ll dis)
{
	typ[u]=flag;scnt[u][flag]++;ct[flag]++;
	cnt[flag]+=dis;bool tflag=0;
	cnt[flag]%=MOD;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		tflag=1;
		dfs(v,u,!flag,dis+1);
		scnt[u][0]+=scnt[v][0];
		scnt[u][1]+=scnt[v][1];
	}
	if(!tflag)scnt[u][flag]=1;
}
void dfs2(ll u,ll fa,ll cntj,ll cnto)
{
	cntj%=MOD;cnto%MOD;
	ans[u]=((cntj%MOD)*(cnto%MOD))%MOD;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		dfs2(v,u,(cntj+ct[1]-2*scnt[v][1])%MOD,(cnto+ct[0]-2*scnt[v][0])%MOD);
	}
}
signed main()
{
	scanf("%lld",&n);loop(i,1,n)e[i].clear();
	loop(i,1,n-1){
		ll u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0,0,0);
	cnt[0]%=MOD,cnt[1]%=MOD;
	dfs2(1,0,cnt[1],cnt[0]);
	loop(i,1,n)
	{
		printf("%lld\n",(ans[i]+MOD)%MOD);
	}
	return 0;
}

首先是个人都能看出来本题正解时间复杂度是线性的

• $10\ pts$ ~ $30\ pts$ :

对每个点枚举两个点，计算合法路径的权值和即可

时间复杂度$O(n^4)$，可通过树上前缀和优化为$O(n^3)$

• $50\ pts$ :

通过对题目的观察可以知道，选取某个点 $u$ 时，树上的点可以被分为两类：与 $u$ 的距离为奇数的点和与 $u$ 的距离为偶数的点，分别对应题目中的 $s(u,x)=0$ 和 $s(u,x)=1$。

设奇数点与 $u$ 的距离总和为 $s_1$，偶数点与选取点距离总和为 $s_2$ 则对于 $u$，答案就是 $s_1\times s_2$。

对每个点进行一次dfs即可得到所有答案。

时间复杂度$O(n^2)$

• $100\ pts$

由于对每个点 $u$ 的答案为 $s_1\times s_2$, 考虑先以一个点为根求出该点的 $s_1$ 与 $s_2$，然后再进行一次dfs，对每个儿子修改 $s_1$ 和 $s_2$ （具体看代码），然后记录每个点的答案。

时间复杂度$O(n)$

考试的时候被取模卡没了10pts

AC代码：

#include<bits/stdc++.h>
#define loop(x,l,r) for(ll (x) = (l);(x)<=(r);++(x))
#define elif else if
using namespace std;
using ll = __int128_t;
#define N 500005
#define MOD 720021013ll
vector<ll> e[N];
ll cnt[2],n;
ll scnt[N][2];
ll typ[N],ct[N];
ll ans[N];
void dfs(ll u,ll fa,ll flag,ll dis)
{
	typ[u]=flag;scnt[u][flag]++;ct[flag]++;
	cnt[flag]+=dis;bool tflag=0;
	cnt[flag]%=MOD;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		tflag=1;
		dfs(v,u,!flag,dis+1);
		scnt[u][0]+=scnt[v][0];
		scnt[u][1]+=scnt[v][1];
	}
	if(!tflag)scnt[u][flag]=1;
}
void dfs2(ll u,ll fa,ll cntj,ll cnto)
{
	cntj%=MOD;cnto%MOD;
	ans[u]=((cntj%MOD)*(cnto%MOD))%MOD;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		dfs2(v,u,(cntj+ct[1]-2*scnt[v][1])%MOD,(cnto+ct[0]-2*scnt[v][0])%MOD);
	}
}
signed main()
{
	scanf("%lld",&n);loop(i,1,n)e[i].clear();
	loop(i,1,n-1){
		ll u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0,0,0);
	cnt[0]%=MOD,cnt[1]%=MOD;
	dfs2(1,0,cnt[1],cnt[0]);
	loop(i,1,n)
	{
		printf("%lld\n",(ans[i]+MOD)%MOD);
	}
	return 0;
}