救救孩子吧
调了3天了死活没调出来
找了3篇题解拍了800000组数据
CPU使用率由10%到99%(拍的)
一直0分(Wa)
#include<bits/stdc++.h>
using namespace std;
long long n,m,cnt=0,head[200000],a[200000],t[200000],depth[200000],siz[200000],son[200000],x[200000],father[200000],num[200000],roadto[200000];
const int QAQ=0;
char s[10];
struct xianduantree
{
long long l,r,lz,lzc,maxn;
}tree[1000000];
struct bian
{
long long to,nxt,w;
}b[3000000];
void add(int u,int v,int w)
{
b[++cnt].to=v;
b[cnt].nxt=head[u];
b[cnt].w=w;
head[u]=cnt;
}
void dfs1(int u,int fa)
{
int i=head[u],v;
siz[u]=1;
while(i!=0)
{
v=b[i].to;
if(v==fa)
{
i=b[i].nxt;
continue;
}
father[v]=u;
depth[v]=depth[u]+1;
roadto[i]=v;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
{
son[u]=v;
}
i=b[i].nxt;
}
}
void dfs2(int u,int fa)
{
int i=head[u],v;
if(son[u]==0)
{
return;
}
else
{
x[son[u]]=++cnt;
t[son[u]]=fa;
num[cnt]=a[son[u]];
dfs2(son[u],fa);
}
while(i!=0)
{
v=b[i].to;
if(v!=father[u]&&v!=son[u])
{
x[v]=++cnt;
num[cnt]=a[v];
t[v]=v;
dfs2(v,v);
}
i=b[i].nxt;
}
return;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void download(int pos)
{
if(tree[pos].lzc!=0)
{
tree[pos*2].lz=tree[pos*2+1].lz=0;
tree[pos*2].lzc=tree[pos*2+1].lzc=tree[pos].lzc;
tree[pos*2].maxn=tree[pos*2+1].maxn=tree[pos].lzc;
tree[pos].lzc=tree[pos].lz=0;
}
else
{
if(tree[pos].lz!=0)
{
tree[pos*2].lz+=tree[pos].lz;
tree[pos*2+1].lz+=tree[pos].lz;
tree[pos*2].maxn+=tree[pos].lz;
tree[pos*2+1].maxn+=tree[pos].lz;
tree[pos].lz=tree[pos].lzc=0;
}
}
}
void build(int pos,int l,int r)
{
tree[pos].l=l;
tree[pos].r=r;
if(l==r)
{
tree[pos].maxn=num[l];
return;
}
build(pos*2,l,(l+r)/2);
build(pos*2+1,(l+r)/2+1,r);
tree[pos].maxn=max(tree[pos*2].maxn,tree[pos*2+1].maxn);
}
void update_cover(int pos,int l,int r,int d)
{
if(r<l)swap(l,r);
if(r<tree[pos].l||l>tree[pos].r)
{
return;
}
else
{
if(l<=tree[pos].l&&tree[pos].r<=r)
{
tree[pos].maxn=d;
tree[pos].lz=0;
tree[pos].lzc=d;
}
else
{
download(pos);
update_cover(pos*2,l,r,d);
update_cover(pos*2+1,l,r,d);
tree[pos].maxn=max(tree[pos*2].maxn,tree[pos*2+1].maxn);
}
}
}
void update_add(int pos,int l,int r,int d)
{
if(r<l)swap(l,r);
if(r<tree[pos].l||l>tree[pos].r)
{
return;
}
else
{
download(pos);
if(l<=tree[pos].l&&tree[pos].r<=r)
{
tree[pos].maxn+=d;
if(tree[pos].lzc==0)tree[pos].lz=d;
else tree[pos].lzc+=d;
}
else
{
update_add(pos*2,l,r,d);
update_add(pos*2+1,l,r,d);
tree[pos].maxn=max(tree[pos*2].maxn,tree[pos*2+1].maxn);
}
}
}
long long find(int pos,int l,int r)
{
if(r<l)swap(l,r);
if(l>tree[pos].r||r<tree[pos].l)
{
return 0;
}
else
{
if(l<=tree[pos].l&&tree[pos].r<=r)
{
return tree[pos].maxn;
}
else
{
download(pos);
return max(find(pos*2,l,r),find(pos*2+1,l,r));
}
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
long long ask_find(long long aa,long long bb)
{
long long ans=0;
while(t[aa]!=t[bb])
{
if(depth[t[aa]]<depth[t[bb]])
{
swap(aa,bb);
}
ans=max(ans,find(1,x[t[aa]],x[aa]));
aa=father[t[aa]];
}
if(depth[aa]<depth[bb])
{
swap(aa,bb);
}
if(aa!=bb)ans=max(ans,find(1,x[son[bb]],x[aa]));
else ans=max(0LL,ans);
return ans;
}
void ask_update_add(long long aa,long long bb,long long d)
{
while(t[aa]!=t[bb])
{
if(depth[t[aa]]<depth[t[bb]])
{
swap(aa,bb);
}
update_add(1,x[t[aa]],x[aa],d);
aa=father[t[aa]];
}
if(depth[aa]<depth[bb])
{
swap(aa,bb);
}
if(aa!=bb)update_add(1,x[son[bb]],x[aa],d);
// else update_add(1,x[aa],x[aa],d);
}
void ask_update_cover(long long aa,long long bb,long long d)
{
while(t[aa]!=t[bb])
{
if(depth[t[aa]]<depth[t[bb]])
{
swap(aa,bb);
}
update_cover(1,x[t[aa]],x[aa],d);
aa=father[t[aa]];
}
if(depth[aa]<depth[bb])
{
swap(aa,bb);
}
if(aa!=bb)update_cover(1,x[son[bb]],x[aa],d);
// else update_cover(1,x[aa],x[aa],d);
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out1.txt","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n-1;++i)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
cnt=0;
depth[1]=1;
dfs1(1,0);
for(int i=1;i<=2*n-2;i++)
{
if(roadto[i]!=0)
{
a[roadto[i]]=b[i].w;
}
}
t[++cnt]=1;
num[cnt]=a[1];
x[1]=cnt;
father[1]=1;
dfs2(1,1);
build(1,1,n);
while(true)
{
long long aa,bb,d;
scanf("%s",s+1);
if(s[1]=='M')
{
scanf("%lld%lld",&aa,&bb);
printf("%lld\n",ask_find(aa,bb));
}
else if(s[1]=='C')
{
if(s[2]=='h')//CHANGE
{
int road;
scanf("%d%lld",&road,&d);
if(roadto[road*2]!=0)
{
aa=bb=roadto[road*2];
update_cover(1,x[aa],x[bb],d);
}
else
{
aa=bb=roadto[road*2-1];
update_cover(1,x[aa],x[bb],d);
}
}
else//COVER
{
scanf("%lld%lld%lld",&aa,&bb,&d);
ask_update_cover(aa,bb,d);
}
}
else if(s[1]=='A')
{
scanf("%lld%lld%lld",&aa,&bb,&d);
ask_update_add(aa,bb,d);
}
else if(s[1]=='S')
{
break;
}
/*
CHANGE u t :把节点 权值改为 ;
QMAX u v :询问点 到点 路径上的节点的最大权值;
QSUM u v :询问点 到点 路径上的节点的权值和。
*/
}
return QAQ;
}
/*
10
1 2 14
2 3 15
2 4 25
4 5 4
3 6 3
4 7 8
1 8 13
2 9 8
3 10 10
Cover 3 4 3
Max 2 3
Stop
*/