Luogu P4114 Qtree1

树剖一好题。我心水了ww

题目描述

给定一棵n个节点的树，有两个操作：

CHANGE i ti 把第i条边的边权变成ti

QUERY a b 输出从a到b的路径中最大的边权，当a=b的时候，输出0

输入输出格式

输入格式：

第一行输入一个n，表示节点个数

第二行到第n行每行输入三个数，ui，vi，wi，分别表示 ui，vi有一条边，边权是wi

第n+1行开始，一共有不定数量行，每一行分别有以下三种可能

CHANGE，QUERY同题意所述

DONE表示输入结束

输出格式：

对于每个QUERY操作，输出一个数，表示a b之间边权最大值

树链剖分维护。若对应的一组父亲节点\(x\)与子节点\(y\)之间有一条边，则将边权存为\(y\)点的点权。在dfs2内特殊处理即可。

对于修改，线段树动态维护一下最大值。

查询路径最大值按照常规树剖的跳链写法就可以了。由于是边权存为点权，不能计算最近公共祖先。\(LCA\)所代表的那条边并不在路径上qwq

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#define MAXN 102333

using namespace std;

int h[MAXN],tot=0,cnt=0;

int n,m;

struct qwq

{

    int nex,to,w;

    int id;

}e[MAXN<<1];

int ans[MAXN<<2];

int w1[MAXN];

int dep[MAXN],son[MAXN]={},fa[MAXN],top[MAXN],siz[MAXN],id[MAXN];

inline void add(int x,int y,int w,int i)

{

    e[++tot].to=y;

    e[tot].nex=h[x];

    e[tot].w=w;

    e[tot].id=i;

    h[x]=tot;

}

#define leftson cur<<1

#define rightson cur<<1|1

#define mid ((l+r)>>1)

#define push_up ans[cur]=max(ans[leftson],ans[rightson])

inline void build(int cur,int l,int r)

{

    if (l==r)

    {

        ans[cur]=w1[l];

        return;

    }

    build(leftson,l,mid);

    build(rightson,mid+1,r);

    push_up;

}

int tag[MAXN<<2];

#define push_down lazyadd(leftson,tag[cur]); lazyadd(rightson,tag[cur]); tag[cur]=0

inline void lazyadd(int cur,int del)

{

    if (!del) return;

    ans[cur]+=del;

    tag[cur]+=del;

}

void change(int adl,int adr,int cur,int l,int r,int del)

{

    if (adl<=l&&r<=adr)

    {

        ans[cur]=del;

        tag[cur]=del;

        return;

    }

    push_down;

    if (adl<=mid) change(adl,adr,leftson,l,mid,del);

    if (adl>mid) change(adl,adr,rightson,mid+1,r,del);

    push_up;

}

int query(int ql,int qr,int cur,int l,int r)

{

    if (ql<=l&&r<=qr)

    {

        return ans[cur];

    }

    int answ=-23333;

    push_down;

    if (ql<=mid) answ=max(answ,query(ql,qr,leftson,l,mid));

    if (qr>mid) answ=max(answ,query(ql,qr,rightson,mid+1,r));

    return answ;

}

int segid[MAXN];

void dfs_fir(int x,int f,int dept)

{

    fa[x]=f;

    dep[x]=dept;

    siz[x]=1;

    int maxn=-1;

    for (int i=h[x],y;i;i=e[i].nex)

    {

        y=e[i].to;

        if (y==f) continue;

        dfs_fir(y,x,dept+1);

        siz[x]+=siz[y];

        if (siz[y]>maxn)

        {

            son[x]=y;

            maxn=siz[y];

        }

    }

}

void dfs_sec(int x,int ft,int w)

{

    top[x]=ft;

    id[x]=++cnt;

    w1[cnt]=w;

    if (!son[x]) return;

    dfs_sec(son[x],ft,0);

    for (int i=h[x],y;i;i=e[i].nex)

    {

        y=e[i].to;

        if (y==fa[x]) continue;

        if (y==son[x])

        {

            w1[id[son[x]]]=e[i].w;

            segid[e[i].id]=id[son[x]];

            continue;

        }

        dfs_sec(y,y,e[i].w);

        segid[e[i].id]=id[y];

    }

}

inline int query_(int x,int y)

{

    int answer=-23333;

    while (top[x]!=top[y])

    {

        if (dep[top[x]]<dep[top[y]]) swap(x,y);

        answer=max(answer,query(id[top[x]],id[x],1,1,n));

        x=fa[top[x]];

    }

    if (dep[x]>dep[y]) swap(x,y);

    answer=max(answer,query(id[x]+1,id[y],1,1,n));

    return answer;

}

int main()

{

    scanf("%d",&n);

    int x,y,w;

    for (int i=1;i<n;i++)

    {

        scanf("%d%d%d",&x,&y,&w);

        add(x,y,w,i);

        add(y,x,w,i);

    }

    dfs_fir(1,1,1);

    dfs_sec(1,1,0);

    build(1,1,n);

    string s="QWQ";

//	for (int i=1;i<=n;i++)

//	{

//		printf("%d ",w1[id[i]]);

//	}

//	printf("\n\n");

    while (s[0]!='D')

    {

        cin>>s;

        if (s[0]=='D') continue;

        scanf("%d%d",&x,&y);

        if (s[0]=='Q')

        {

            if (x==y)

            {

                printf("0\n");

                continue;

            }

            printf("%d\n",query_(x,y));

            continue;

        }

        change(segid[x],segid[x],1,1,n,y);

    }

    return 0;

}