不败丶流逝 的博客

不败丶流逝 的博客

题解 P4114 【Qtree1】

posted on 2019-10-09 16:22:27 | under 题解 |

这不就是个树剖裸题么

树剖一下,然后用线段树维护区间最大值

每次是单点修改

这道题的难点在于边权怎么处理

我们可以在两点连的边之间新建一个节点,把边的权值赋给它,对于原树上的节点为了不影响赋成-inf

然后这题就做完了

#include<iostream>
#include<cstdio>
#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=100005,inf=1e9;
int n,cnt,tot;
int head[N<<1],siz[N<<1],top[N<<1],fa[N<<1],dep[N<<1],son[N<<1],id[N<<1],vl[N<<1],val[N<<1];
int tr[N<<3];
struct node{
    int to,nxt;
}e[N<<2];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline void add(int from,int to){
    e[++cnt]=(node){to,head[from]};
    head[from]=cnt;
}
void dfs1(int x,int f,int deep){
    fa[x]=f;siz[x]=1;dep[x]=deep;
    int maxson=-1;
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=f){
            dfs1(e[i].to,x,deep+1);
            siz[x]+=siz[e[i].to];
            if(siz[e[i].to]>maxson)son[x]=e[i].to,maxson=siz[e[i].to];
        }
}
void dfs2(int x,int topf){
    id[x]=++tot;val[tot]=vl[x];top[x]=topf;
    if(!son[x])return ;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].to==fa[x]||e[i].to==son[x])continue;
        dfs2(e[i].to,e[i].to);
    }
}
inline void update(int k){
    tr[k]=max(tr[ls],tr[rs]);
}
void change(int k,int l,int r,int x,int y){
    if(l==r&&l==x){
        tr[k]=y;
        return ;
    }
    if(x<=mid)change(lson,x,y);
    else change(rson,x,y);
    update(k);
}
int ask(int k,int l,int r,int x,int y){
    if(l==x&&y==r){
        return tr[k];
    }
    if(y<=mid)return ask(lson,x,y);
    else if(x>mid)return ask(rson,x,y);
    else return max(ask(lson,x,mid),ask(rson,mid+1,y));
}

void build(int k,int l,int r){
    if(l==r){
        tr[k]=val[l];
        return ;
    }
    build(lson);build(rson);
    update(k);
}
int query(int x,int y){
    if(x==y)return 0;
    int ans=-inf;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])x^=y^=x^=y;
        ans=max(ask(1,1,(n<<1)-1,id[top[x]],id[x]),ans);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])x^=y^=x^=y;
    ans=max(ans,ask(1,1,(n<<1)-1,id[y],id[x]));
    return ans;
}
int main(){
    n=read();
    int x,y;
    for(int i=1;i<n;++i){
        x=read();y=read();
        add(x,i+n);add(i+n,x);
        add(y,i+n);add(i+n,y);
        vl[i+n]=read();vl[x]=vl[y]=-inf;
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,(n<<1)-1);
    char c[10];
    while(1){
        scanf("%s",c+1);
        if(c[1]=='D')return 0;
        x=read();y=read();
        if(c[1]=='Q')printf("%d\n",query(x,y));
        else change(1,1,(n<<1)-1,id[x+n],y);
    }
}