为什么会 WA?

P1600 [NOIP2016 提高组] 天天爱跑步

¶凉笙 @ 2021-06-11 17:29:07

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
    T x=0;char ch=getchar();bool fl=false;
    while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
    }
    return fl?-x:x;
}
const int maxn = 3e5 + 10;
int head[maxn],cnt=0;
struct edge{
    int to,nxt;
}e[maxn<<1];
inline void link(int u,int v){
    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
#include <vector>
#define maxlog 23
int n,m;
vector <int> add1[maxn],add2[maxn],del1[maxn],del2[maxn];
int de[maxn],f[maxn][23];
void dfs(int u,int fa){
    de[u]=de[fa]+1;f[u][0]=fa;
    for(int i=1;i<maxlog;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
    }
}
int getlca(int x,int y){
    if(de[x]<de[y])swap(x,y);
    for(int i=maxlog-1;i>=0;i--){
        if(de[f[x][i]]>=de[y])x=f[x][i];
    }
    if(x==y)return x;
    for(int i=maxlog-1;i>=0;i--)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int w[maxn],t1[maxn],t2[maxn],ans[maxn];//从下往上 and 从上往下
void solve(int u,int fa){
    int v1=t1[w[u]+de[u]],v2=t2[w[u]-de[u]+n];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        solve(v,u);
    }
    for(vector<int>::iterator it=add1[u].begin();it!=add1[u].end();it++)t1[*it]++;
    for(vector<int>::iterator it=del1[u].begin();it!=del1[u].end();it++)t1[*it]--;
    for(vector<int>::iterator it=add2[u].begin();it!=add2[u].end();it++)t2[*it]++;
    for(vector<int>::iterator it=del2[u].begin();it!=del2[u].end();it++)t2[*it]--;
    ans[u]+=t1[w[u]+de[u]]-v1+t2[w[u]-de[u]+n]-v2;
}
#define read() read<int>()
#define Debug(x) cerr<<(x)<<endl
int main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();link(u,v),link(v,u);
    }
    for(int i=1;i<=n;i++)w[i]=read();
    de[0]=0;
    dfs(1,0);
    for(int i=1;i<=m;i++){
        int s=read(),t=read();
        int LCA=getlca(s,t);
        //Debug(LCA);//
        add1[s].push_back(de[s]);
        add2[t].push_back(de[s]-2*de[LCA]+n);//细节+n
        del1[LCA].push_back(de[s]);
        del2[f[LCA][0]].push_back(de[s]-2*de[LCA]+n);
    }
    solve(1,0);
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    puts("");
    return 0;
}

by zhuoz @ 2021-06-11 18:03:02

@¶凉笙 你跟我微信头像一样耶!!!


|