#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const long long N=100010;
struct edge
{
long long from,to,Next,val;
}edge[N*2];
long long n,num,cnt;
long long head[N],father[N],son[N],tot[N],idx[N],top[N],dep[N],w[N];
long long tag[N*4],Max[N*4],lazy[N*4];
long long read()
{
char chr;
long long f=1;
while (((chr=getchar())<'0')||(chr>'9'))
{
if (chr=='-')
{
f=-1;
}
}
long long res=chr-'0';
while (((chr=getchar())>='0')&&(chr<='9'))
{
res=res*10+chr-'0';
}
return res*f;
}
void add_edge(long long from,long long to,long long val)
{
edge[++num].Next=head[from];
edge[num].from=from;
edge[num].to=to;
edge[num].val=val;
head[from]=num;
}
void dfs(long long k,long long f,long long deep)
{
long long bigson=0;
father[k]=f;
dep[k]=deep;
tot[k]=1;
for (long long i=head[k];i;i=edge[i].Next)
{
long long v=edge[i].to;
if (v==f)
{
continue;
}
dfs(v,k,deep+1);
tot[k]+=tot[v];
if (bigson<tot[v])
{
bigson=tot[v];
son[k]=v;
}
}
}
void dfs(long long k,long long tp)
{
idx[k]=++cnt;
top[k]=tp;
if (!son[k])
{
return;
}
dfs(son[k],tp);
for (long long i=head[k];i;i=edge[i].Next)
{
long long v=edge[i].to;
if (!idx[v])
{
dfs(v,v);
}
}
}
void pushup(long long now)
{
Max[now]=max(Max[now*2],Max[now*2+1]);
}
inline void pushdown(long long now)
{
if (tag[now]!=-1)
{
Max[now*2]=Max[now*2+1]=tag[now];
tag[now*2]=tag[now*2+1]=tag[now];
lazy[now*2]=lazy[now*2+1]=0;
tag[now]=-1;
}
if (lazy[now])
{
lazy[now*2]+=lazy[now];
lazy[now*2+1]+=lazy[now];
Max[now*2]+=lazy[now];
Max[now*2+1]+=lazy[now];
lazy[now]=0;
}
}
void build(long long l,long long r,long long now)
{
lazy[now]=0;
tag[now]=-1;
if (l==r)
{
Max[now]=w[l];
return;
}
long long mid=(l+r)/2;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
pushup(now);
}
void outchange(long long p,long long l,long long r,long long now,long long c)
{
if (l==r)
{
Max[now]=c;
return;
}
long long mid=(l+r)/2;
pushdown(now);
if (p<=mid)
{
outchange(p,l,mid,now*2,c);
}
else
{
outchange(p,mid+1,r,now*2+1,c);
}
pushup(now);
}
void inchange(long long L,long long R,long long l,long long r,long long now,long long c)
{
if ((l>R)||(r<L))
{
return;
}
if ((l>=L)&&(r<=R))
{
Max[now]=c;
tag[now]=c;
lazy[now]=0;
return;
}
long long mid=(l+r)/2;
pushdown(now);
if (mid>=R)
{
inchange(L,R,l,mid,now*2,c);
}
else
{
if (mid<L)
{
inchange(L,R,mid+1,r,now*2+1,c);
}
else
{
inchange(L,mid,l,mid,now*2,c);
inchange(mid+1,R,mid+1,r,now*2+1,c);
}
}
pushup(now);
}
void inchanges(long long L,long long R,long long l,long long r,long long now,long long c)
{
if ((l>R)||(r<L))
{
return;
}
if ((l>=L)&&(r<=R))
{
Max[now]+=c;
lazy[now]+=c;
return;
}
long long mid=(l+r)/2;
pushdown(now);
if (mid>=R)
{
inchanges(L,R,l,mid,now*2,c);
}
else
{
if (mid<L)
{
inchanges(L,R,mid+1,r,now*2+1,c);
}
else
{
inchanges(L,mid,l,mid,now*2,c);
inchanges(mid+1,R,mid+1,r,now*2+1,c);
}
}
pushup(now);
}
long long getmax(long long L,long long R,long long l,long long r,long long now)
{
if ((l>R)||(r<L))
{
return -1e9;
}
if ((l>=L)&&(r<=R))
{
return Max[now];
}
long long mid=(l+r)/2;
pushdown(now);
if (mid>=R)
{
return getmax(L,R,l,mid,now*2);
}
if (mid<L)
{
return getmax(L,R,mid+1,r,now*2+1);
}
return max(getmax(L,mid,l,mid,now*2),getmax(mid+1,R,mid+1,r,now*2+1));
}
void treechange(long long x,long long y,long long val)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
inchange(idx[top[x]],idx[x],1,n,1,val);
x=father[top[x]];
}
if (dep[x]>dep[y])
{
swap(x,y);
}
inchange(idx[x]+1,idx[y],1,n,1,val);
}
void treechanges(long long x,long long y,long long val)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
inchanges(idx[top[x]],idx[x],1,n,1,val);
x=father[top[x]];
}
if (dep[x]>dep[y])
{
swap(x,y);
}
inchanges(idx[x]+1,idx[y],1,n,1,val);
}
long long treemax(long long x,long long y)
{
long long ans=-1e9;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
ans=max(ans,getmax(idx[top[x]],idx[x],1,n,1));
x=father[top[x]];
}
if (dep[x]>dep[y])
{
swap(x,y);
}
return max(ans,getmax(idx[x]+1,idx[y],1,n,1));
}
int main()
{
n=read();
for (long long i=1;i<n;i++)
{
long long x=read(),y=read(),z=read();
add_edge(x,y,z);
add_edge(y,x,z);
}
dfs(1,0,1);
dfs(1,1);
for (long long i=1;i<=num;i+=2)
{
long long &u=edge[i].from,&v=edge[i].to;
if (dep[u]>dep[v])
{
swap(u,v);
}
w[idx[v]]=edge[i].val;
}
build(1,n,1);
while (1)
{
char key[10];
scanf("%s",key);
if (key[0]=='D')
{
break;
}
long long x=read(),y=read();
if (key[0]=='C')
{
outchange(idx[edge[(x*2)-1].to],1,n,1,y);
}
if (key[0]=='Q')
{
if (x==y)
{
cout<<0<<"\n";
}
printf("%d\n",treemax(x,y));
}
}
return 0;
}
by 桃夭 @ 2018-11-02 11:49:39
```
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const long long N=100010;
struct edge
{
long long from,to,Next,val;
}edge[N*2];
long long n,num,cnt;
long long head[N],father[N],son[N],tot[N],idx[N],top[N],dep[N],w[N];
long long tag[N*4],Max[N*4],lazy[N*4];
long long read()
{
char chr;
long long f=1;
while (((chr=getchar())<'0')||(chr>'9'))
{
if (chr=='-')
{
f=-1;
}
}
long long res=chr-'0';
while (((chr=getchar())>='0')&&(chr<='9'))
{
res=res*10+chr-'0';
}
return res*f;
}
void add_edge(long long from,long long to,long long val)
{
edge[++num].Next=head[from];
edge[num].from=from;
edge[num].to=to;
edge[num].val=val;
head[from]=num;
}
void dfs(long long k,long long f,long long deep)
{
long long bigson=0;
father[k]=f;
dep[k]=deep;
tot[k]=1;
for (long long i=head[k];i;i=edge[i].Next)
{
long long v=edge[i].to;
if (v==f)
{
continue;
}
dfs(v,k,deep+1);
tot[k]+=tot[v];
if (bigson<tot[v])
{
bigson=tot[v];
son[k]=v;
}
}
}
void dfs(long long k,long long tp)
{
idx[k]=++cnt;
top[k]=tp;
if (!son[k])
{
return;
}
dfs(son[k],tp);
for (long long i=head[k];i;i=edge[i].Next)
{
long long v=edge[i].to;
if (!idx[v])
{
dfs(v,v);
}
}
}
void pushup(long long now)
{
Max[now]=max(Max[now*2],Max[now*2+1]);
}
inline void pushdown(long long now)
{
if (tag[now]!=-1)
{
Max[now*2]=Max[now*2+1]=tag[now];
tag[now*2]=tag[now*2+1]=tag[now];
lazy[now*2]=lazy[now*2+1]=0;
tag[now]=-1;
}
if (lazy[now])
{
lazy[now*2]+=lazy[now];
lazy[now*2+1]+=lazy[now];
Max[now*2]+=lazy[now];
Max[now*2+1]+=lazy[now];
lazy[now]=0;
}
}
void build(long long l,long long r,long long now)
{
lazy[now]=0;
tag[now]=-1;
if (l==r)
{
Max[now]=w[l];
return;
}
long long mid=(l+r)/2;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
pushup(now);
}
void outchange(long long p,long long l,long long r,long long now,long long c)
{
if (l==r)
{
Max[now]=c;
return;
}
long long mid=(l+r)/2;
pushdown(now);
if (p<=mid)
{
outchange(p,l,mid,now*2,c);
}
else
{
outchange(p,mid+1,r,now*2+1,c);
}
pushup(now);
}
void inchange(long long L,long long R,long long l,long long r,long long now,long long c)
{
if ((l>R)||(r<L))
{
return;
}
if ((l>=L)&&(r<=R))
{
Max[now]=c;
tag[now]=c;
lazy[now]=0;
return;
}
long long mid=(l+r)/2;
pushdown(now);
if (mid>=R)
{
inchange(L,R,l,mid,now*2,c);
}
else
{
if (mid<L)
{
inchange(L,R,mid+1,r,now*2+1,c);
}
else
{
inchange(L,mid,l,mid,now*2,c);
inchange(mid+1,R,mid+1,r,now*2+1,c);
}
}
pushup(now);
}
void inchanges(long long L,long long R,long long l,long long r,long long now,long long c)
{
if ((l>R)||(r<L))
{
return;
}
if ((l>=L)&&(r<=R))
{
Max[now]+=c;
lazy[now]+=c;
return;
}
long long mid=(l+r)/2;
pushdown(now);
if (mid>=R)
{
inchanges(L,R,l,mid,now*2,c);
}
else
{
if (mid<L)
{
inchanges(L,R,mid+1,r,now*2+1,c);
}
else
{
inchanges(L,mid,l,mid,now*2,c);
inchanges(mid+1,R,mid+1,r,now*2+1,c);
}
}
pushup(now);
}
long long getmax(long long L,long long R,long long l,long long r,long long now)
{
if ((l>R)||(r<L))
{
return -1e9;
}
if ((l>=L)&&(r<=R))
{
return Max[now];
}
long long mid=(l+r)/2;
pushdown(now);
if (mid>=R)
{
return getmax(L,R,l,mid,now*2);
}
if (mid<L)
{
return getmax(L,R,mid+1,r,now*2+1);
}
return max(getmax(L,mid,l,mid,now*2),getmax(mid+1,R,mid+1,r,now*2+1));
}
void treechange(long long x,long long y,long long val)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
inchange(idx[top[x]],idx[x],1,n,1,val);
x=father[top[x]];
}
if (dep[x]>dep[y])
{
swap(x,y);
}
inchange(idx[x]+1,idx[y],1,n,1,val);
}
void treechanges(long long x,long long y,long long val)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
inchanges(idx[top[x]],idx[x],1,n,1,val);
x=father[top[x]];
}
if (dep[x]>dep[y])
{
swap(x,y);
}
inchanges(idx[x]+1,idx[y],1,n,1,val);
}
long long treemax(long long x,long long y)
{
long long ans=-1e9;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
ans=max(ans,getmax(idx[top[x]],idx[x],1,n,1));
x=father[top[x]];
}
if (dep[x]>dep[y])
{
swap(x,y);
}
return max(ans,getmax(idx[x]+1,idx[y],1,n,1));
}
int main()
{
n=read();
for (long long i=1;i<n;i++)
{
long long x=read(),y=read(),z=read();
add_edge(x,y,z);
add_edge(y,x,z);
}
dfs(1,0,1);
dfs(1,1);
for (long long i=1;i<=num;i+=2)
{
long long &u=edge[i].from,&v=edge[i].to;
if (dep[u]>dep[v])
{
swap(u,v);
}
w[idx[v]]=edge[i].val;
}
build(1,n,1);
while (1)
{
char key[10];
scanf("%s",key);
if (key[0]=='D')
{
break;
}
long long x=read(),y=read();
if (key[0]=='C')
{
outchange(idx[edge[(x*2)-1].to],1,n,1,y);
}
if (key[0]=='Q')
{
if (x==y)
{
cout<<0<<"\n";
}
printf("%d\n",treemax(x,y));
}
}
return 0;
}
```
by 桃夭 @ 2018-11-02 11:49:53
希望更丰富的展现？使用Markdown
by RiverFun @ 2018-11-02 11:50:02
不是妹子，不回答qwq
by 夢·壹生所愛 @ 2018-11-02 11:54:00
啊我知道了漏了个continue
by 桃夭 @ 2018-11-02 11:54:36
@[Steve_braveman](/space/show?uid=96570) 谢谢了qwq
by 桃夭 @ 2018-11-02 11:55:00
蒟蒻表示 当我看到我的代码超过4k的时候 我就知道我要写挂了qwq
by 花里心爱 @ 2018-11-02 12:00:18
@[Irressey](/space/show?uid=79017) 写还好，查错的时候可能想死qwq
by 桃夭 @ 2018-11-02 12:06:16
你为什么要强调你不是妹子
by 曾宇康 @ 2018-11-02 12:07:16
希望更丰富的展现？使用Markdown
by callG @ 2018-11-02 12:09:41