TLE on18求助
查看原帖
TLE on18求助
740329
sunaohua楼主2023/3/16 10:14

是我写假了吗

#define orz GCC
#pragma orz optimize("Ofast,-falign-functions,-falign-jumps,-falign-labels,-falign-loops,-fcaller-saves,-fcrossjumping,-fcse-follow-jumps,-fdelete-null-pointer-checks,-fdevirtualize,-fexpensive-optimizations,-ffast-math,-fgcse,-fgcse-lm,-fhoist-adjacent-loads,-findirect-inlining,-finline,-fipa-sra,-fno-stack-protector,-foptimize-sibling-calls,-fpartial-inlining,-fpeephole2,-freorder-blocks,-freorder-functions,-frerun-cse-after-loop,-fsched-interblock,-fsched-spec,-fschedule-insns,-fschedule-insns2,-fstrict-aliasing,-fthread-jumps,-ftree-pre,-ftree-switch-conversion,-ftree-tail-merge,-ftree-vrp,-funroll-loops")
#pragma orz target("abm,avx,mmx,popcnt,sse,sse2,sse3,sse4,ssse3,tune=native")
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+15;
int col[maxn];
long long ans[maxn];
int z[maxn];
vector<int> zz[maxn];
int son[maxn];
int w[maxn];
int cnt[maxn];
int tot=0;
long long mx,sum,Son;
inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x;
}
void add(int a,int fa,int val){
	cnt[col[a]]+=val;
	if(cnt[col[a]]>mx){
	mx=cnt[col[a]],sum=col[a];	
	} 
	else if(cnt[col[a]]==mx)sum+=col[a];
	for(int i=0;i<z[a];i++){
	int to=zz[a][i];
	if(to==fa||to==Son)
	continue;
	add(to,a,val);
	}
}
void dfs1(int fa,int a){
//	cout<<a;
	int maxnum=0;int maxx=0;
	for(int i=0;i<z[a];i++){
	int to=zz[a][i];
	if(to==fa)
	continue;
	dfs1(to,a);
	w[a]+=w[to];
	if(w[to]>maxx){
	maxx=w[to];
	maxnum=to;
	}
	}
	son[a]=maxnum;
}
void dfs2(int a,int fa,int flag){
	
	for(int i=0;i<z[a];i++){
	int to=zz[a][i];
	if(to==fa||to==son[a])
	continue;
	dfs2(to,a,0);
	}
	if(son[a]){
	dfs2(son[a],a,1);
	Son=son[a];	
	}
	add(a,fa,1);
	ans[a]=sum;
	if(!flag){
	add(a,fa,-1),sum=0,mx=0;	
	}
}
int main(){
 	int n;
 	cin>>n;
 	for(int i=1;i<=n;i++)
 	col[i]=read();
	for(int i=1;i<n;i++){
	int u,v;
	u=read(),v=read();
	z[u]++;z[v]++;
	zz[u].push_back(v);
	zz[v].push_back(u);
	}
	dfs1(1,-1);
	dfs2(1,-1,0);
	for(int i=1;i<=n;i++)
	printf("%lld ",ans[i]);
	return 0;
}
2023/3/16 10:14
加载中...