@[yjf1225](/user/1069395) bsoj上你真的是这份代码吗
by Enoch006 @ 2024-03-15 20:50:13
@[yjf1225](/user/1069395) 我好像看出错误了
by lcbridge @ 2024-03-15 20:53:00
@[Enoch006](/user/538683)
bsoj上题目有点不一样，是下面这份代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
namespace akioi{
const long long N=1e6+10;
const long long INF=0x3f3f3f3f;
long long n;
long long h[N],ne[2*N],e[2*N],w[2*N],o[2*N],idx;
long long sz[N],maxx[N],g[N];
long long dfn[N],idx_dfn,sa[N];
long long top[N],dep[N],fa[N],hei[N];
long long Root,a[N],yjf[N];
struct node{
long long maxx;
}tree[4*N];
void up(long long k){
tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
}
void build(long long k,long long l,long long r){
if(l==r){
tree[k].maxx=dfn[l];
return ;
}
long long mid=(l+r)>>1;
build(2*k,l,mid);
build(2*k+1,mid+1,r);
up(k);
}
long long query(long long k,long long l,long long r,long long L,long long R){
if(r<L || R<l) return 0;
if(L<=l && r<=R){
return tree[k].maxx;
}
long long mid=(l+r)>>1;
return max(query(2*k,l,mid,L,R),query(2*k+1,mid+1,r,L,R));
}
void modify(long long k,long long l,long long r,long long L,long long d){
if(r<L || L<l) return ;
if(l==r){
tree[k].maxx=d;
return ;
}
long long mid=(l+r)>>1;
modify(2*k,l,mid,L,d);
modify(2*k+1,mid+1,r,L,d);
up(k);
}
void add(long long x,long long y,long long z,long long k){
e[++idx]=y;
w[idx]=z;
o[idx]=k;
ne[idx]=h[x];
h[x]=idx;
}
void dfs1(long long u,long long de,long long last){
yjf[u]=last;
sz[u]=1;
for(long long i=h[u];i!=-1;i=ne[i]){
if(last==o[i]) continue;
dep[o[i]]=de;
dfs1(e[i],de+1,o[i]);
sz[u]+=sz[e[i]];
fa[o[i]]=last;
if(sz[e[i]]>=maxx[u]){
maxx[u]=sz[e[i]];
g[u]=i;
}
}
}
void dfs2(long long u,long long tp,long long last){
// cout<<u<<' '<<last<<'\n';
if(g[u]!=0){
dfn[++idx_dfn]=w[g[u]];
sa[o[g[u]]]=idx_dfn;
top[o[g[u]]]=tp;
dfs2(e[g[u]],tp,o[g[u]]);
}
for(long long i=h[u];i!=-1;i=ne[i]){
if(o[i]!=last && i!=g[u]){
dfn[++idx_dfn]=w[i];
top[o[i]]=o[i];
sa[o[i]]=idx_dfn;
dfs2(e[i],o[i],o[i]);
}
}
}
long long query_lca(long long x,long long y){
long long ans=0;
while(top[x]!=top[y]){
// cout<<"!!!";
if(dep[top[x]]>dep[top[y]]){
ans=max(query(1,1,n,sa[top[x]],sa[x]),ans);
// cout<<"DDD"<<sa[top[x]]<<' '<<sa[x]<<'\n';
x=fa[top[x]];
}
else{
ans=max(query(1,1,n,sa[top[y]],sa[y]),ans);
// cout<<"DDD"<<sa[top[y]]<<' '<<sa[y]<<'\n';
y=fa[top[y]];
}
}
if(dep[x]>dep[y]){
ans=max(ans,query(1,1,n,sa[y]+1,sa[x]));
// cout<<sa[y]+1<<' '<<sa[x]<<'\n';
}
else{
ans=max(ans,query(1,1,n,sa[x]+1,sa[y]));
// cout<<x<<' '<<y<<' '<<sa[x]+1<<' '<<sa[y]<<'\n';
}
return ans;
}
long long main(){
memset(h,-1,sizeof(h));
long long m;
scanf("%lld%lld",&n,&m);
long long x,y,z;
for(long long i=1;i<n;i++){
scanf("%lld%lld%lld",&x,&y,&z);
z++;
add(x,y,z,i);
add(y,x,z,i);
// if(z==0) return 0;
}
dfn[++idx_dfn]=0;
sa[0]=1;
dfs1(1,1,0);
// cout<<"!!!";
dfs2(1,1,0);
build(1,1,n);
// for(long long i=1;i<=n;i++){
// cout<<fa[i]<<'\n';
// }
long long op;
for(long long i=1;i<=m;i++){
scanf("%lld%lld%lld",&op,&x,&y);
if(op==0){
modify(1,1,n,sa[x],y+1);
}
else{
if(x==y || n==1) printf("-1\n");
else{
// cout<<yjf[x]<<' '<<yjf[y]<<'\n';
long long tmp=query_lca(yjf[x],yjf[y]);
printf("%lld\n",tmp-1);
}
}
}
return 0;
}
}
signed main(){
return akioi::main();
}
/*
5 1
1 2 1
2 3 100
3 4 2
1 5 3
1 5 2
*/
```
by yjf1225 @ 2024-03-15 20:53:05
@[yjf1225](/user/1069395) 你问Enoch006
by lcbridge @ 2024-03-15 20:53:25
@[lcbridge](/user/546681)
什么？
by yjf1225 @ 2024-03-15 20:53:45
@[Enoch006](/user/538683)
请问我的代码有什么错误？
by yjf1225 @ 2024-03-15 20:55:50
@[yjf1225](/user/1069395) 有一个点是sa[y]+1有可能大于a[x]
by Enoch006 @ 2024-03-15 20:58:25
@[yjf1225](/user/1069395) 改了过后bsoj上有20分了/kk
by Enoch006 @ 2024-03-15 20:58:58
@[Enoch006](/user/538683)
请问那该如何改呢？
by yjf1225 @ 2024-03-15 21:00:14
@[Enoch006](/user/538683)
我之前就有20分了
by yjf1225 @ 2024-03-15 21:00:47