a's'da'd'sa'd
  • 板块灌水区
  • 楼主shufeng2007
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/31 22:00
  • 上次更新2024/8/31 22:01:44
查看原帖
a's'da'd'sa'd
1124817
shufeng2007楼主2024/8/31 22:00
#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int h[N],e[2*N],ne[2*N],idx;
struct E{
int a,b;
}edge[2*N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int f[N][2];
int n;
int dfs(int u,int fa){
	f[u][1]=1;
	f[u][0]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa) continue;
		dfs(j,u);
		f[u][0]*=f[j][0]+f[j][1];
		f[u][1]*=f[j][0];
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++) cin>>edge[i].a>>edge[i].b;
	for(int i=1;i<n;i++){
		idx=0;
		memset(h,-1,sizeof h);
		memset(e,0,sizeof e);
		memset(ne,0,sizeof ne);
		memset(f,0,sizeof f);
		for(int j=1;j<n;j++){
			if(j==i) continue;
			add(edge[j].a,edge[j].b);
			add(edge[j].b,edge[j].a);
		}
		dfs(edge[i].a,-1);
		dfs(edge[i].b,-1);
		cout<<f[edge[i].a][0]*f[edge[i].b][1]+f[edge[i].a][1]*f[edge[i].b][0]+f[
		edge[i].a][1]*f[edge[i].b][1]<<endl;
	}
	return 0;
}
2024/8/31 22:00
加载中...