_maze @ 2020-09-01 23:16:58
这道题下面有一大段,讲述关于怎么样会MLE,怎么避免MLE。但我们老师说,这些东西在平时评测时不会出现。
于是我信心满满地交了一份DFS部分分代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,s[30000],f[30000],ti[30000],ton[30000],d[30000],p[30000];
int to[30000*2],st[30000*2],nx[30000*2],tot;
void add(int u,int v){
to[++tot]=v;
nx[tot]=st[u];
st[u]=tot;
}
void dfs(int u,int fa){
for(int i=st[u];i;i=nx[i]){
int v=to[i];
if(v==fa) continue;
p[v]=u;
d[v]=d[u]+1;
dfs(v,u);
}
}
void dfs1(int u,int fin,int time){
// cout<<"$$$ "<<u<<' '<<fin<<' '<<time<<endl;
if(ti[u]==time){
ton[u]++;
}
if(u==fin){
return;
}
dfs1(p[u],fin,time+1);
}
void dfs2(int u,int fin,int time){
// cout<<"$$$ "<<u<<' '<<fin<<' '<<time<<endl;
if(ti[u]==time){
ton[u]++;
}
if(u==fin){
return;
}
dfs2(p[u],fin,time-1);
}
bool dfs4(int u,int fin){
if(u==fin){
return 1;
}
if(u==1){
return 0;
}
return dfs4(p[u],fin);
}
int main(){
// freopen("running.in","r",stdin);
// freopen("running.out","w",stdout);
// cout<<pow(2,0);
cin>>n>>m;
int u,v;
for(int i=1;i<n;i++){
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
cin>>ti[i];
}
for(int i=1;i<=m;i++){
cin>>s[i]>>f[i];
}
dfs(1,-1);
for(int i=1;i<=m;i++){
if(dfs4(s[i],f[i])==0&&dfs4(f[i],s[i])==0){
int bef=ton[1];
dfs1(s[i],1,0);
if(ton[1]!=bef) ton[1]--;
dfs2(f[i],1,d[f[i]]+d[s[i]]);
}
else{
if(d[s[i]]>d[f[i]]) dfs1(s[i],f[i],0);
else dfs2(f[i],s[i],d[f[i]]-d[s[i]]);
}
}
for(int i=1;i<=n;i++){
cout<<ton[i]<<' ';
}
// }
}
但很奇怪,MLE了。
所以有大佬为我说一下这是为什么吗?
by eaten_apple @ 2020-09-09 21:05:17
好孤寂啊