QwQ_77 @ 2024-03-29 21:43:00

#include<bits/stdc++.h>
using namespace std;
int n,m; 
int fa[300000];//双亲表示法 
int w[300000][3];//记录观察员出现时间和每个观察员会观察到多少人
int te[300000];//临时数组（用于记录） 
struct H
{
    int s,t;
    int time[30000];
}h[15000];//记录每个节点的起点、终点和每一秒所到达的点 
void init()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        fa[v]=u; 
    }
}
void HH()
{
    int temp=1;//临时变量 
    for(int i=1;i<=m;i++)
        cin>>h[i].s>>h[i].t;
    for(int i=1;i<=n;i++)
    {   
        te[temp]==fa[h[i].t];
        temp++;
    }
    int cnt=1;
    for(int i=1;i<=temp;i++)
    for(int j=temp;j>=1;j--)
        h[i].time[cnt]=te[j];
}
void see()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(h[j].time[w[i][1]]=i)
            w[i][2]++;
    }
}
int main()
{
    init();
    for(int i=1;i<=n;i++)
    {
        cin>>w[i][1];
        w[i][2]=0;
    }
    HH();
    see();
    for(int i=1;i<=n;i++)
        cout<<w[i][2]<<" ";
    return 0;
}

by QwQ_77 @ 2024-03-30 12:49:23

修改结构体数组h大小之后，结果有改变

by QwQ_77 @ 2024-03-30 12:50:22

但还是0分qwq

by HEROBRINEH @ 2024-04-07 21:28:31

@QwQ_77 AC 求关

#include <bits/stdc++.h>
#define N 300005
#define int long long
#define endl '\n'
using namespace std;
int n,m;
vector <int> g[N];
vector <int> rec1[N],rec2[N],del1[N],del2[N];
int d[N],f[N][30],w[N],ans[N],c1[N<<2],c2[N<<2];
void dfs(int u,int fa) {
    d[u]=d[fa]+1,f[u][0]=fa;
    for (int i=1;i<=25;i++){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for (int i=0; i<g[u].size(); i++) {
        int v=g[u][i];
        if (v==fa) continue;
        dfs(v,u);
    }
}
int lca(int x,int y){
    if (d[x]<d[y]) swap(x,y);
    for (int i=25;i>=0;i--){
        if (d[f[x][i]]>=d[y]) x=f[x][i];
    }
    if (x==y) return x;
    for (int i=25;i>=0;i--){
        if (f[x][i]!=f[y][i]){
            x=f[x][i],y=f[y][i];
        }
    }
    return f[x][0];
}
void dfs2(int u,int fa) {
    int tmp1=c1[d[u]+w[u]+N],tmp2=c2[w[u]-d[u]+N];
    for (int i=0; i<g[u].size(); i++) {
        int v=g[u][i];
        if (v==fa) continue;
        dfs2(v,u);
    }
    for (int i=0;i<rec1[u].size();i++){
        int v=rec1[u][i];
        c1[v]++;
    }
    for (int i=0;i<rec2[u].size();i++){
        int v=rec2[u][i];
        c2[v]++;
    }
    ans[u]+=c1[d[u]+w[u]+N]-tmp1;
    ans[u]+=c2[w[u]-d[u]+N]-tmp2;
    for (int i=0;i<del1[u].size();i++){
        int v=del1[u][i];
        c1[v]--;
    }
    for (int i=0;i<del2[u].size();i++){
        int v=del2[u][i];
        c2[v]--;
    }
}
signed main (){
    int i,x,y;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for (i=1; i<n; i++) {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    d[1]=1;
    dfs(1,0);
    for (i=1;i<=n;i++){
        cin>>w[i];
    }
    for (i=1;i<=m;i++){
        cin>>x>>y;
        int k=lca(x,y);
        rec1[x].push_back(d[x]+N),rec2[y].push_back(d[x]-2*d[k]+N),del1[k].push_back(d[x]+N),del2[k].push_back(d[x]-2*d[k]+N);
        if (d[k]+w[k]==d[x]) ans[k]--;
    }
    dfs2(1,0);
    for (i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

by QwQ_77 @ 2024-04-07 21:32:24

@HEROBRINEH

蟹蟹！！！！！！！（惊呼

尖叫）（扭曲）（阴暗的爬行） （爬行）（扭动）（阴暗地蠕动）（翻滚）（激烈地爬动）（扭曲）（痉挛）（嘶吼）（蠕动）（阴森的低吼）（爬行）（分裂）（走上岸）（扭动）（痉挛）（蠕动）（扭曲的行走）（不分对象攻击）（尖叫）（扭曲）（阴暗的爬行） （爬行）（扭动）（阴暗地蠕动）（翻滚）（激烈地爬动）（扭曲）（痉挛）（嘶吼）（蠕动）（阴森的低吼）（爬行）（分裂）（走上岸）（扭动）（痉挛）（蠕动）（扭曲的行走）（不分对象攻击）（尖叫）（扭曲）（阴暗的爬行） （爬行）（扭动）（阴暗地蠕动）（翻滚）（激烈地爬动）（扭曲）（痉挛）（嘶吼）（蠕动）（阴森的低吼）（爬行）（分裂）（走上岸）（扭动）（痉挛）（蠕动）（扭曲的行走）（不分对象攻击）

已关qaq

by QwQ_77 @ 2024-04-07 21:33:08

@HEROBRINEH 关注了

by QwQ_77 @ 2024-04-09 22:06:58

@HEROBRINEH

花了点时间看代码。。。

可以讲讲思路吗orz

我太蒻了