修改结构体数组h大小之后,结果有改变
by QwQ_77 @ 2024-03-30 12:49:23
但还是0分qwq
by QwQ_77 @ 2024-03-30 12:50:22
@[QwQ_77](/user/1055521) AC 求关
```cpp
#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 HEROBRINEH @ 2024-04-07 21:28:31
@[HEROBRINEH](/user/1113507)
蟹蟹!!!!!!!(惊呼
尖叫)(扭曲)(阴暗的爬行) (爬行)(扭动)(阴暗地蠕动)(翻滚)(激烈地爬动)(扭曲)(痉挛)(嘶吼)(蠕动)(阴森的低吼)(爬行)(分裂)(走上岸)(扭动)(痉挛)(蠕动)(扭曲的行走)(不分对象攻击)(尖叫)(扭曲)(阴暗的爬行) (爬行)(扭动)(阴暗地蠕动)(翻滚)(激烈地爬动)(扭曲)(痉挛)(嘶吼)(蠕动)(阴森的低吼)(爬行)(分裂)(走上岸)(扭动)(痉挛)(蠕动)(扭曲的行走)(不分对象攻击)(尖叫)(扭曲)(阴暗的爬行) (爬行)(扭动)(阴暗地蠕动)(翻滚)(激烈地爬动)(扭曲)(痉挛)(嘶吼)(蠕动)(阴森的低吼)(爬行)(分裂)(走上岸)(扭动)(痉挛)(蠕动)(扭曲的行走)(不分对象攻击)
已关qaq
by QwQ_77 @ 2024-04-07 21:32:24
@[HEROBRINEH](/user/1113507) 关注了
by QwQ_77 @ 2024-04-07 21:33:08
@[HEROBRINEH](/user/1113507)
花了点时间看代码。。。
可以讲讲思路吗orz
~~我太蒻了~~
by QwQ_77 @ 2024-04-09 22:06:58