题目
大数据全挂，救救孩子吧
#include<bits/stdc++.h>
const int N=1e6;
using namespace std;
int ls(int p){return (p<<1);}
int rs(int p){return (p<<1)+1;}
int m,n,a[N],w[N],tree[N],lazy_add[N],lazy_assign[N];
int cnt,head[N],dfn;
pair<int,int> ed[N];
struct edge{
int next,to,w;
}e[N*2];
void add_edge(int u,int v,int w){
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].w=w;
head[u]=cnt;
}
struct node{
int size,top,son,dep,fa,id;
}p[N];
void dfs1(int u,int fa){
p[u].fa=fa;
p[u].dep=p[fa].dep+1;
p[u].size=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(v==fa) continue;
dfs1(v,u); a[v]=w;
p[u].size+=p[v].size;
if(p[u].son==0||p[v].size>p[p[u].son].size){
p[u].son=v;
}
}
}
void dfs2(int u,int t){
p[u].id=++dfn;
p[u].top=t;
if(!p[u].son) return;
dfs2(p[u].son,t);
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==p[u].fa||v==p[u].son) continue;
dfs2(v,v);
}
}
void pushup(int p){
tree[p]=max(tree[ls(p)],tree[rs(p)]);
}
void assign(int p,int k){
tree[p]=k;
lazy_add[p]=0;//覆盖区间加
lazy_assign[p]=k;
}
void add(int p,int pl,int pr,int k){
tree[p]+=(pr-pl+1)*k;
lazy_add[p]=k;
}
void pushdown(int p,int pl,int pr){
if(lazy_assign[p]>=0){//先进行推平
assign(ls(p),lazy_assign[p]);
assign(rs(p),lazy_assign[p]);
lazy_assign[p]=-1;
}
if(lazy_add[p]){
int mid=(pl+pr)>>1;
add(ls(p),pl,mid,lazy_add[p]);
add(rs(p),mid+1,pr,lazy_add[p]);
lazy_add[p]=0;
}
}
int get_w(int k){
return (p[ed[k].first].dep>p[ed[k].second].dep)?p[ed[k].first].id:p[ed[k].second].id;
//因为将权值传给了儿子节点(儿子节点深度更深)，所以便是儿子的dfn序
}
void build(int p,int pl,int pr){
if(pl==pr){tree[p]=w[pl];return;}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
pushup(p);
}
void update_assign(int p,int pl,int pr,int l,int r,int k){//区间推平
if(l<=pl&&pr<=r){assign(p,k);return;}
int mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) update_assign(ls(p),pl,mid,l,r,k);
if(mid+1<=r) update_assign(rs(p),mid+1,pr,l,r,k);
pushup(p);
}
void update_add(int p,int pl,int pr,int l,int r,int k){
if(l<=pl&&pr<=r){add(p,pl,pr,k);return;}
int mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) update_add(ls(p),pl,mid,l,r,k);
if(mid+1<=r) update_add(rs(p),mid+1,pr,l,r,k);
pushup(p);
}
int query(int p,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r){return tree[p];}
int res=0,mid=(pl+pr)>>1;
pushdown(p,pl,pr);
if(l<=mid) res=max(res,query(ls(p),pl,mid,l,r));
if(mid+1<=r) res=max(res,query(rs(p),mid+1,pr,l,r));
return res;
}
void tree_assign(int x,int y,int k){
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
update_assign(1,1,n,p[p[x].top].id,p[x].id,k);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
if(p[y].id<p[x].id)update_assign(1,1,n,p[y].id+1,p[x].id,k);//边是记录在儿子上的,所以只能从儿子开始改
}
void tree_add(int x,int y,int k){
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
update_add(1,1,n,p[p[x].top].id,p[x].id,k);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
if(p[y].id<p[x].id) update_add(1,1,n,p[y].id+1,p[x].id,k);//边是记录在儿子上的,所以只能从儿子开始改
}
int tree_query(int x,int y){
int res=0;
while(p[x].top!=p[y].top){
if(p[p[x].top].dep<p[p[y].top].dep) swap(x,y);
res=max(res,query(1,1,n,p[p[x].top].id,p[x].id));
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep) swap(x,y);
if(p[y].id<p[x].id) return max(res,query(1,1,n,p[p[y].son].id,p[x].id));
return res;
}
int main(){
memset(lazy_assign,-1,sizeof(lazy_assign));
cin>>n;
for(int i=1;i<=n-1;i++){
int x,y,z;
cin>>x>>y>>z;
ed[i].first=x;ed[i].second=y;
add_edge(x,y,z);
add_edge(y,x,z);
}
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=n;i++){
w[p[i].id]=a[i];
}
build(1,1,n);
while(1){
string m;int x,y,z;
cin>>m;
if(m=="Stop") break;
else if(m=="Change"){
cin>>x>>z;
update_assign(1,1,n,get_w(x),get_w(x),z);
}
else if(m=="Cover"){
cin>>x>>y>>z;
tree_assign(x,y,z);
}
else if(m=="Add"){
cin>>x>>y>>z;
tree_add(x,y,z);
}
else{
cin>>x>>y;
cout<<tree_query(x,y)<<endl;
}
}
return 0;
}