start_from_scratch @ 2024-07-28 10:26:45
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int MN=300005;
ll n,m,u,v,tot,head[MN],w[MN],s,t,fa[20][MN],deep[MN],ans[MN],c[MN],lca;
struct edge{ll nxt,to;}e[MN<<2];
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void add(ll u, ll v){e[++tot].nxt=head[u];head[u]=tot;e[tot].to=v;}
void lca_dfs(ll u, ll f){
deep[u]=deep[f]+1;fa[u][0]=f;
for(int i=1; (1<<i)<=deep[u]; i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u]; i; i=e[i].nxt) if(e[i].to!=f) lca_dfs(e[i].to,u);
}
ll LCA(ll u, ll v){
if(deep[u]<deep[v]) swap(u,v);
for(int i=19; i>=0; i--) if(deep[u]-(1<<i)>=deep[v]){
c[u]++,c[fa[u][i]]--;
u=fa[u][i];
}
if(u==v) return u;
for(int i=19; i>=0; i--) if(fa[u][i]!=fa[v][i]){
c[u]++,c[fa[u][i]]--;
c[v]++,c[fa[v][i]]--;
u=fa[u][i],v=fa[v][i];
}
c[u]++,c[fa[u][0]]--;
c[v]++,c[fa[v][0]]--;
return fa[u][0];
}
void dfs1(ll f, ll s){
if(s==lca) return;
c[f]=c[s]+1;
for(int i=head[f]; i; i=e[i].nxt) if(e[i].to==fa[f][0]) dfs1(e[i].to,f);
}
void dfs2(ll f, ll s){
if(s==lca) return;
for(int i=head[f]; i; i=e[i].nxt) if(e[i].to==fa[f][0]) dfs2(e[i].to,f);
c[s]=c[f]+1;
}
int main(){
n=read();m=read();
for(int i=1; i<n; i++){
u=read();v=read();
add(u,v);add(v,u);
}
for(int i=1; i<=n; i++) w[i]=read();
lca_dfs(1,0);
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++) c[j]=-1;
s=read();t=read();
if(s!=t){lca=LCA(s,t);c[lca]+=2;dfs1(fa[s][0],s);dfs2(fa[t][0],t);}
else c[s]=0;
for(int j=1; j<=n; j++) if(c[j]==w[j]) ans[j]++;
}
for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
return 0;
}
by keatsli @ 2024-07-29 19:04:24
好像你的fa整个就开反了
by keatsli @ 2024-07-29 19:05:31
改完后会tle,但至少能过几个点了。
by keatsli @ 2024-07-29 19:06:30
因为你的时间复杂度是错的,具体正确算法可以参考题解。
by keatsli @ 2024-07-29 19:07:11
可以通过构造一条链来卡掉你
by start_from_scratch @ 2024-07-29 21:30:31
@keatsli 已关,谢谢