powerfire @ 2019-03-03 15:33:39
#include<bits/stdc++.h>
using namespace std;
const long long N=100005;
struct Tree{
long long L,R,max;
}tree[N<<2];
struct Edge{
long long to,next;
}edge[N<<1];
long long en,head[N];
long long father[N],son[N],size[N];
long long seg[N],rev[N],top[N];
long long u[N],v[N],w[N],n,Max,depth[N];
void add(long long x,long long y){
edge[en].to=y;
edge[en].next=head[x];
head[x]=en++;
}
void init(){
memset(head,-1,sizeof(head));
scanf("%lld",&n);
for(long long i=1;i<n;i++){
scanf("%lld%lld%lld",&u[i],&v[i],&w[i]);
add(u[i],v[i]);
add(v[i],u[i]);
}
}
void dfs1(long long u,long long f){
father[u]=f;
depth[u]=depth[f]+1;
size[u]=1;
for(long long p=head[u],v;~p;p=edge[p].next){
v=edge[p].to;
if(v!=f){
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])
son[u]=v;
}
}
}
void dfs2(long long u){
if(son[u]){
seg[son[u]]=++seg[0];
top[son[u]]=top[u];
rev[seg[0]]=son[u];
dfs2(son[u]);
}
for(long long p=head[u],v;~p;p=edge[p].next){
v=edge[p].to;
if(!top[v]){
seg[v]=++seg[0];
top[v]=v;
rev[seg[0]]=v;
dfs2(v);
}
}
}
void pushup(long long root){
tree[root].max=max(tree[root<<1].max,tree[root<<1|1].max);
}
void create(long long root,long long L,long long R){
tree[root].L=L;tree[root].R=R;tree[root].max=-0x7fffffff;
if(L==R)return;
long long mid=L+R>>1;
create(root<<1,L,mid);
create(root<<1|1,mid+1,R);
}
void change(long long root,long long x,long long k){
if(tree[root].L==tree[root].R){
tree[root].max=k;
return;
}
long long mid=tree[root].L+tree[root].R>>1;
if(mid>=x)change(root<<1,x,k);
else change(root<<1|1,x,k);
pushup(root);
}
void query(long long root,long long x,long long y){
if(tree[root].L>y||tree[root].R<x)return;
if(tree[root].L>=x&&tree[root].R<=y){
Max=max(Max,tree[root].max);
return;
}
query(root<<1,x,y);
query(root<<1|1,x,y);
}
void chaxun(long long x,long long y){
if(x==y)return;
long long fx(top[x]),fy(top[y]);
while(fx!=fy){
if(depth[fx]<depth[fy])swap(x,y),swap(fx,fy);
query(1,seg[fx],seg[x]);
x=father[fx];
fx=top[x];
}
if(depth[x]>depth[y])swap(x,y);
if(x!=y)query(1,seg[x]+1,seg[y]);
else return;
}
int main(){
init();
dfs1(1,0);
rev[1]=seg[0]=seg[1]=top[1]=1;
dfs2(1);
char cmd[10];
create(1,1,seg[0]);
for(long long i=1;i<n;i++){
if(depth[u[i]]>depth[v[i]])swap(u[i],v[i]);
change(1,seg[v[i]],w[i]);
}
while(scanf("%s",cmd+1)){
long long x,y;
switch(cmd[1]){
case 'C':scanf("%lld%lld",&x,&y);change(1,seg[v[x]],y);break;
case 'Q':scanf("%lld%lld",&x,&y);chaxun(x,y);printf("%lld\n",Max);Max=-0x7fffffff;break;
case 'D':return 0;
}
}
}by Smile_Cindy @ 2019-03-03 15:35:24
@powerfire
树状数组，信我的没错。
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define int LL
#define lowbit(i) ((i)&(-(i)))
using namespace std;
typedef long long LL;
const int MAX_N=100005;
int n,m;
vector <int> g[MAX_N];
int bel[MAX_N];
int siz[MAX_N];
int depth[MAX_N];
int W[MAX_N];
int sum[MAX_N];
int dfn[MAX_N];
int Index;
int f[MAX_N][21];
int A[MAX_N];
int to[MAX_N];
pair<int,int> edge[MAX_N];
int dfs_(int v,int fa)
{
f[v][0]=fa;
depth[v]=depth[fa]+1;
siz[v]=1;
for(int i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(u==fa)continue;
siz[v]+=dfs_(u,v);
}
return siz[v];
}
void dfs(int v,int chain)
{
dfn[v]=++Index;
bel[v]=chain;
int k=0;
for(int i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(depth[u]==depth[v]+1 && siz[u]>siz[k])k=u;
}
if(k)dfs(k,chain);
for(int i=0;i<g[v].size();i++)
{
int u=g[v][i];
if(depth[u]==depth[v]+1 && u!=k)dfs(u,u);
}
}
struct BIT
{
int bit[MAX_N];
void init()
{
memset(bit,0,sizeof(bit));
}
void modify(int i,int x)
{
A[i]=x;
while(i<=n)
{
bit[i]=A[i];
for(int j=1;j<lowbit(i);j<<=1)
{
bit[i]=max(bit[i],bit[i-j]);
}
i+=lowbit(i);
}
}
int query(int l,int r)
{
if(r<l)return 0;
int ans=A[r];
while(true)
{
ans=max(ans,A[r]);
if(r<=l) break;
r--;
while(r-l>=lowbit(r))
{
ans=max(ans,bit[r]);
r-=lowbit(r);
}
}
return ans;
}
}bit;
int lca(int u,int v)
{
if(depth[u]<depth[v])swap(u,v);
int t=depth[u]-depth[v];
for(int j=20;j>=0;j--)
{
if(t&(1<<j))u=f[u][j];
}
if(u==v)return v;
for(int j=20;j>=0;j--)
{
if(f[u][j]!=f[v][j])
{
u=f[u][j];
v=f[v][j];
}
}
return f[u][0];
}
int read()
{
char ch=' ';
int x=0;
bool flag=false;
while(!isdigit(ch))
{
if(ch=='-')flag=true;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return flag?-x:x;
}
signed main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
edge[i]=make_pair(u,v);
g[u].push_back(v);
g[v].push_back(u);
W[i]=read();
}
dfs_(1,0);
dfs(1,1);
for(int i=1;i<n;i++)
{
int u,v;
u=edge[i].first;
v=edge[i].second;
if(depth[u]<depth[v])swap(u,v);
bit.modify(dfn[u],W[i]);
to[i]=u;
}
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
}
}
while(true)
{
string opt;
cin>>opt;
if(opt=="CHANGE")
{
int u=read(),w=read();
bit.modify(dfn[to[u]],w);
}
else if(opt=="QUERY")
{
int u=read(),v=read();
int t=lca(u,v);
int ans=0;
while(bel[u]!=bel[t])
{
ans=max(ans,bit.query(dfn[bel[u]],dfn[u]));
u=f[bel[u]][0];
}
ans=max(ans,bit.query(dfn[t]+1,dfn[u]));
while(bel[v]!=bel[t])
{
ans=max(ans,bit.query(dfn[bel[v]],dfn[v]));
v=f[bel[v]][0];
}
ans=max(ans,bit.query(dfn[t]+1,dfn[v]));
printf("%lld\n",ans);
}
else break;
}
return 0;
}