目录

[TOC]

题面
题目链接

题目描述

输入输出格式
输入格式

输出格式

输入输出样例
输入样例：

输出样例：

说明

思路

AC代码

总结

题面

题目链接

题目描述

Ray 乐忠于旅游，这次他来到了 T城。T城是一个水上城市，一共有 $ N $ 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T城的任意两个景点之间有且只有一条路径。换句话说， T城中只有 $ N − 1 $ 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度 $ w $，也就是说，Ray 经过这座桥会增加 $ w $ 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从 $ u $　景点到 $ v $ 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

输入输出格式

输入格式

输入的第一行包含一个整数 $ N $，表示 T城中的景点个数。景点编号为 0...N − 1。

接下来 $N − 1 $ 行，每行三个整数 $ u $ 、$ v $ 和 $ w $ ，表示有一条 $ u $ 到 $ v $ ，使 Ray 愉悦度增加 $ w $ 的桥。桥的编号为1...N − 1。|w| $ \leq $ 1000。输入的第 $ N + 1

$ 行包含一个整数 $ M $ ，表示Ray 的操作数目。

接下来有 $ M $ 行，每行描述了一个操作，操作有如下五种形式：

C $ i $ $ w $，表示Ray 对于经过第 $ i $ 座桥的愉悦度变成了 $ w $ 。

N $ u $ $ v $ ，表示Ray 对于经过景点 $ u $ 到 $ v $ 的路径上的每一座桥的愉悦度都变成原来的相反数。

SUM $ u $ $ v $ ，表示询问从景点 $ u $ 到 $ v $ 所获得的总愉悦度。

MAX $ u $ $ v $ ，表示询问从景点 $ u $ 到 $ v $ 的路径上的所有桥中某一座桥所提供的最大愉悦度。

MIN $ u $ $ v $ ，表示询问从景点 $ u $ 到 $ v $ 的路径上的所有桥中某一座桥所提供的最小愉悦度。

测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。

输出格式

对于每一个询问(操作S、MAX 和MIN)，输出答案。

输入输出样例

输入样例：

3

0 1 1

1 2 2

8

SUM 0 2

MAX 0 2

N 0 1

SUM 0 2

MIN 0 2

C 1 3

SUM 0 2

MAX 0 2

输出样例：

说明

【时空限制】

1000ms,128M

思路

首先貌似要加个条件，好像没给数据范围。。。N $ \leq $ 100000 吧

题意参考如下

给定一棵树，每条边有一个边权，有如下5个操作

C 修改某一条边的权值

N 将从u到v路径上所有边边权修改为其相反数

SUM 统计从u到v路径上所有边边权和

MAX 统计从u到v路径上所有边边权的最大值

MIN 统计从u到v路径上所有边边权的最小值

操作很多，要维护一堆东西。边权转点权如果不懂可以先做这个题 P4114 Qtree1 这里主要说一下线段树的部分。

由于维护和，最大值，最小值，首先每个结构体肯定有l,r,sum，max，min；这里C操作是单点修改边，而N操作是区间修改，所以需要一个tag来存是否要全部变为-1，且tag初始值为1，每次N操作就要给区间的tag乘上-1。下传时，下传条件是t(p)==-1，sum取相反数，max是原来min的相反数，min是原来max的相反数

剩下的，码就完了（这是一道debug题）

AC代码

#include<bits/stdc++.h>

const int maxn=100010;

using namespace std;

int n,m,w[maxn];

int tot,wt[maxn],to[maxn<<1],nxt[maxn<<1],head[maxn];

int son[maxn],fa[maxn],dep[maxn],len[maxn];

int cnt,top[maxn],nid[maxn],nw[maxn];

struct BuildTree

{

    int l,r,mx,mi,sum,tag;

    #define l(a) tree[a].l

    #define r(a) tree[a].r

    #define m(a) ((l(a)+r(a))>>1)

    #define s(a) tree[a].sum

    #define t(a) tree[a].tag

    #define mx(a) tree[a].mx

    #define mi(a) tree[a].mi

}tree[maxn<<2];

int read() ///又看到0开头，逼我学快读

{

    int lsk=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}

    while(isdigit(ch)) lsk=(lsk<<3)+(lsk<<1)+(ch-'0'),ch=getchar();

    return f*lsk;

}

void dfs1(int u,int f,int d)

{

    fa[u]=f;dep[u]=d;len[u]=1;

    for(int i=head[u];i;i=nxt[i])

    {

        int v=to[i];

        if(v==f) continue;

        dfs1(v,u,d+1);

        len[u]+=len[v];

        if(len[v]>len[son[u]]) son[u]=v;

    }

}

void dfs2(int p,int t)

{

    top[p]=t;nid[p]=++cnt;

    if(!son[p]) return;

    dfs2(son[p],t);

    for(int i=head[p];i;i=nxt[i])

    {

        int v=to[i];

        if(v==fa[p] || v==son[p]) continue;

        dfs2(v,v);

    }

}

void Update(int p)

{

    s(p)=s(p<<1)+s(p<<1|1);

    mx(p)=max(mx(p<<1),mx(p<<1|1));

    mi(p)=min(mi(p<<1),mi(p<<1|1));

}

void BuildTree(int p,int l,int r)

{

    l(p)=l;r(p)=r;t(p)=1;

    if(l==r)

    {

        s(p)=mx(p)=mi(p)=nw[l];

        return;

    }

    BuildTree(p<<1,l,m(p));

    BuildTree(p<<1|1,m(p)+1,r);

    Update(p);

}

void R(int p)

{

    s(p)=-s(p);

    swap(mi(p),mx(p));

    mi(p)=-mi(p);

    mx(p)=-mx(p);

    t(p)*=-1;

}

void PushDown(int p)

{

    if(t(p)==-1)

    {

        R(p<<1);

        R(p<<1|1);

        t(p)=1;

    }

}

void SC(int np,int p,int k) ///SingleChange

{

    if(l(np)==r(np))

    {

        s(np)=mx(np)=mi(np)=k;

        return;

    }

    PushDown(np);

    if(p<=m(np)) SC(np<<1,p,k);

    if(p>m(np)) SC(np<<1|1,p,k);

    Update(np);

}

void RC1(int p,int l,int r) ///ReverseChange

{

    if(l<=l(p) && r>=r(p))

    {

        R(p);

        return;

    }

    PushDown(p);

    if(l<=m(p)) RC1(p<<1,l,r);

    if(r>m(p)) RC1(p<<1|1,l,r);

    Update(p);

}

void RC2(int u,int v)

{

    while(top[u]!=top[v])

    {

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        RC1(1,nid[top[u]],nid[u]);

        u=fa[top[u]];

    }

    if(u==v) return;

    if(dep[u]>dep[v]) swap(u,v);

    RC1(1,nid[u]+1,nid[v]);

}

int GS1(int p,int l,int r) ///GetSum

{

    if(l<=l(p) && r>=r(p)) return s(p);

    PushDown(p);

    int ans=0;

    if(l<=m(p)) ans+=GS1(p<<1,l,r);

    if(r>m(p)) ans+=GS1(p<<1|1,l,r);

    return ans;

}

int GS2(int u,int v)

{

    int ans=0;

    while(top[u]!=top[v])

    {

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        ans+=GS1(1,nid[top[u]],nid[u]);

        u=fa[top[u]];

    }

    if(u==v) return ans;

    if(dep[u]>dep[v]) swap(u,v);

    ans+=GS1(1,nid[u]+1,nid[v]);

    return ans;

}

int GMX1(int p,int l,int r) ///GetMax

{

    if(l<=l(p) && r>=r(p)) return mx(p);

    PushDown(p);

    int ans=INT_MIN;

    if(l<=m(p)) ans=max(ans,GMX1(p<<1,l,r));

    if(r>m(p)) ans=max(ans,GMX1(p<<1|1,l,r));

    return ans;

}

int GMX2(int u,int v)

{

    int ans=INT_MIN;

    while(top[u]!=top[v])

    {

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        ans=max(ans,GMX1(1,nid[top[u]],nid[u]));

        u=fa[top[u]];

    }

    if(u==v) return ans;

    if(dep[u]>dep[v]) swap(u,v);

    ans=max(ans,GMX1(1,nid[u]+1,nid[v]));

    return ans;

}

int GMI1(int p,int l,int r) ///GetMin

{

    if(l<=l(p) && r>=r(p)) return mi(p);

    PushDown(p);

    int ans=INT_MAX;

    if(l<=m(p)) ans=min(ans,GMI1(p<<1,l,r));

    if(r>m(p)) ans=min(ans,GMI1(p<<1|1,l,r));

    return ans;

}

int GMI2(int u,int v)

{

    int ans=INT_MAX;

    while(top[u]!=top[v])

    {

        if(dep[top[u]]<dep[top[v]]) swap(u,v);

        ans=min(ans,GMI1(1,nid[top[u]],nid[u]));

        u=fa[top[u]];

    }

    if(u==v) return ans;

    if(dep[u]>dep[v]) swap(u,v);

    ans=min(ans,GMI1(1,nid[u]+1,nid[v]));

    return ans;

}

int main()

{

    n=read();

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

    {

        int u,v,w;

        u=read()+1;

        v=read()+1;

        w=read();wt[i]=w;

        to[++tot]=v;nxt[tot]=head[u];head[u]=tot;

        to[++tot]=u;nxt[tot]=head[v];head[v]=tot;

    }

    dfs1(1,1,1);

    dfs2(1,1);

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

    {

        int u=to[(i<<1)-1],v=to[i<<1];

        if(dep[u]<dep[v]) nw[nid[v]]=wt[i];

        else nw[nid[u]]=wt[i];

    }

    BuildTree(1,1,n);

    m=read();

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

    {

        string way;int u,v;

        cin>>way;u=read()+1;v=read()+1;

        if(way=="C")

        {

            u--,v--;

            int a=to[(u<<1)-1],b=to[u<<1];

            if(dep[a]<dep[b]) SC(1,nid[b],v);

            else SC(1,nid[a],v);

        }

        else if(way=="N") RC2(u,v);

        else if(way=="SUM") printf("%d\n",GS2(u,v));

        else if(way=="MAX") printf("%d\n",GMX2(u,v));

        else printf("%d\n",GMI2(u,v));

    }

    return 0;

}

总结

码量很大的题目，ctrl+c别忘了改其中的东西

巴特西

洛谷 P1505 [国家集训队]旅游树链剖分

目录

[TOC]

题面
题目链接

题目描述

输入输出格式
输入格式

输出格式

输入输出样例
输入样例：

输出样例：

说明

思路

AC代码

总结

题面

题目链接

题目描述

输入输出格式

输入格式

输出格式

输入输出样例

输入样例：

输出样例：

说明

思路

AC代码

总结

最新文章

热门文章

巴特西

洛谷 P1505 [国家集训队]旅游 树链剖分

目录 [TOC] 题面 题目链接 题目描述 输入输出格式 输入格式 输出格式 输入输出样例 输入样例： 输出样例： 说明 思路 AC代码 总结

题面

题目链接

题目描述

输入输出格式

输入格式

输出格式

输入输出样例

输入样例：

输出样例：

说明

思路

AC代码

总结

最新文章

热门文章

洛谷 P1505 [国家集训队]旅游树链剖分

目录

[TOC]

题面
题目链接

题目描述

输入输出格式
输入格式

输出格式

输入输出样例
输入样例：

输出样例：

说明

思路

AC代码

总结