Tobiichi_Origami @ 2022-11-18 07:31:54
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next,w;
}ed[1000001];
int he[1000001],tot;
int w[1000001];
struct tree{
int l,r;
int maxx=-11451414;
}t[1000001];
int dfn[1000001],idx;
int son[1000001];
int dep[1000001];
int top[1000001];
int siz[1000001];
int wei[1000001];
int fa[1000001];
int n;
void insert(int u,int v,int w)
{
tot++;
ed[tot].to=v;
ed[tot].w=w;
ed[tot].next=he[u];
he[u]=tot;
}
void dfs_son(int u,int father)
{
dep[u]=dep[father]+1;siz[u]=1;
fa[u]=father;
for(int i=he[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
if(v!=father)
{
w[v]=ed[i].w;
dfs_son(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
return ;
}
void dfs_order(int u,int t)
{
dfn[u]=++idx;wei[idx]=w[u];
top[u]=t;
if(!son[u]) return ;
dfs_order(son[u],t);
for(int i=he[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
if(v!=fa[u]&&v!=son[u])
dfs_order(v,v);
}
return ;
}
void pushup(int u)
{
int tmp=max(t[u<<1].maxx,t[u<<1|1].maxx);
t[u].maxx=tmp;
}
void build(int u,int l,int r)
{
t[u].l=l;t[u].r=r;
if(l==r)
{
t[u].maxx=wei[l];
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
return ;
}
void modify(int u,int pos,int val)
{
if(t[u].l==t[u].r)
{
t[u].maxx=val;
return ;
}
int mid=(t[u].l+t[u].r)>>1;
if(pos<=mid) modify(u<<1,pos,val);
else modify(u<<1|1,pos,val);
pushup(u);
return ;
}
int query(int u,int l,int r)
{
if(t[u].l>=l&&t[u].r<=r)
return t[u].maxx;
int mid=(t[u].l+t[u].r)>>1;
int res=0;
if(mid>=l) res=max(res,query(u<<1,l,r));
if(mid<r) res=max(res,query(u<<1|1,l,r));
return res;
}
int query_path(int u,int v)
{
if(x==y) return 0;
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
res=max(res,query(1,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dfn[u]<dfn[v])
swap(u,v);
res=max(res,query(1,dfn[v],dfn[u]));
return res;
}
int main()
{
memset(he,-1,sizeof(he));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
}
dfs_son(1,-1);
dfs_order(1,1);
build(1,1,n);
char op[8];
while(scanf("%s",op)&&op[0]!='D')
{
int x,y;
scanf("%d %d",&x,&y);
if(op[0]=='Q') printf("%d\n",query_path(x,y));
else modify(1,dfn[x],y);
}
return 0;
}qwq
by Tobiichi_Origami @ 2022-11-18 07:55:11
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next,w;
}ed[5000001];
int he[5000001],tot;
int w[5000001];
struct tree{
int l,r;
int maxx=-11451414;
}t[5000001];
int dfn[5000001],idx;
int son[5000001];
int dep[5000001];
int top[5000001];
int siz[5000001];
int wei[5000001];
int fa[5000001];
int n;
void insert(int u,int v,int w)
{
tot++;
ed[tot].to=v;
ed[tot].w=w;
ed[tot].next=he[u];
he[u]=tot;
}
void dfs_son(int u,int father)
{
dep[u]=dep[father]+1;siz[u]=1;
fa[u]=father;
for(int i=he[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
if(v!=father)
{
w[v]=ed[i].w;
dfs_son(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
return ;
}
void dfs_order(int u,int t)
{
dfn[u]=++idx;wei[idx]=w[u];
top[u]=t;
if(!son[u]) return ;
dfs_order(son[u],t);
for(int i=he[u];i!=-1;i=ed[i].next)
{
int v=ed[i].to;
if(v!=fa[u]&&v!=son[u])
dfs_order(v,v);
}
return ;
}
void pushup(int u)
{
int tmp=max(t[u<<1].maxx,t[u<<1|1].maxx);
t[u].maxx=tmp;
}
void build(int u,int l,int r)
{
t[u].l=l;t[u].r=r;
if(l==r)
{
t[u].maxx=wei[l];
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
return ;
}
void modify(int u,int pos,int val)
{
if(t[u].l==t[u].r)
{
t[u].maxx=val;
return ;
}
int mid=(t[u].l+t[u].r)>>1;
if(pos<=mid) modify(u<<1,pos,val);
else modify(u<<1|1,pos,val);
pushup(u);
return ;
}
int query(int u,int l,int r)
{
if(t[u].l>=l&&t[u].r<=r)
return t[u].maxx;
int mid=(t[u].l+t[u].r)>>1;
int res=0;
if(mid>=l) res=max(res,query(u<<1,l,r));
if(mid<r) res=max(res,query(u<<1|1,l,r));
return res;
}
int query_path(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
res=max(res,query(1,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dfn[u]<dfn[v])
swap(u,v);
res=max(res,query(1,dfn[v],dfn[u]));
return res;
}
int main()
{
memset(he,-1,sizeof(he));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
}
dfs_son(1,-1);
dfs_order(1,1);
build(1,1,n);
char op[8];
while(scanf("%s",op)&&op[0]!='D')
{
int x,y;
scanf("%d %d",&x,&y);
if(x==y){puts("0");continue;}
if(op[0]=='Q') printf("%d\n",query_path(x,y));
else
{
if(fa[y]==x) swap(x,y);
modify(1,dfn[x],y);
}
}
return 0;
}发错了，这个是
by UYHW @ 2022-11-18 07:57:55
3
1 2 5
2 3 3
QUERY 2 3
DONE