当前位置:网站首页>P1505 [National Training Team] Tourism Tree Chain Breakdown
P1505 [National Training Team] Tourism Tree Chain Breakdown
2022-08-09 07:05:00 【swust_fang】
题目链接
题意:Update the weight of a certain point on the tree,Update the two-point simple path weights,查询最大,最小,和
思路:思路应该比较简单,That is, after the tree chain is divided, the line segment tree is used to maintain the maximum and minimum intervals and the interval sum.
But what is special about this question is the given edge right,It can be converted into points.But query or update two pointsx,ywhen passing between,x,y的lcaThe edge corresponding to the point weight of the point is
fathar[lca]--->lca这条边,不属于x->y的简单路径.
So when updating or querying,当处理到x,ybelong to the same chain
This process speaks of a queryx->y,x,y一直往上跳,until there is a jump tolca时(若dep[x]<dep[y],x就是lca)
这时x,ybelongs to a continuous interval,又因xPoint weights do not count,就是更新(dfn[x]+1,y),dfn为时间戳
So it is a relatively basic tree chain division.
但是,This damn code,也太恶心了,我就写了一个bug,Searched for two hours?,wc
一个update1写成updateI really can't find it...我太难了
//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
//freopen("E://1.in","r",stdin);
//freopen("E://1.out","w",stdout);
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
//const int mod=1e9+7;
const int maxn=2e5+5;
int d[maxn],f[maxn],dfn[maxn],tim[maxn],top[maxn],size[maxn],son[maxn],a[maxn];
int head[maxn],sign;
char s[3];
struct node
{
int to,p,val;
}edge[maxn<<1];
struct nod
{
int mx,mi,sum;
}tree[maxn<<2];
int lazy[maxn<<2];
int n,t;
void init()
{
for(int i=0;i<=n;i++) head[i]=-1;
sign=t=0;
}
void add(int u,int v,int val)
{
edge[sign]=node{v,head[u],val};
head[u]=sign++;
}
void dfs1(int u,int pre,int step)
{
d[u]=step;
f[u]=pre;
size[u]=1;
for(int i=head[u];~i;i=edge[i].p)
{
int v=edge[i].to;
if(v==pre) continue;
a[v]=edge[i].val;
dfs1(v,u,step+1);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp)
{
dfn[u]=++t;
tim[t]=u;
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(int i=head[u];~i;i=edge[i].p)
{
int v=edge[i].to;
if(v!=f[u]&&v!=son[u]) dfs2(v,v);
}
}
void pushup(int i,int l,int r)
{
tree[i].sum=tree[lson].sum+tree[rson].sum;
tree[i].mx=max(tree[lson].mx,tree[rson].mx);
tree[i].mi=min(tree[lson].mi,tree[rson].mi);
}
void pushdown(int i,int l,int r)
{
if(lazy[i])
{
tree[lson].sum=-tree[lson].sum;
tree[rson].sum=-tree[rson].sum;
int t1=tree[lson].mx,t2=tree[rson].mx,s1=tree[lson].mi,s2=tree[rson].mi;
tree[lson].mx=-s1,tree[rson].mx=-s2,tree[lson].mi=-t1,tree[rson].mi=-t2;
lazy[lson]^=1;
lazy[rson]^=1;
lazy[i]=0;
}
}
void build(int i,int l,int r)
{
if(l==r)
{
tree[i].sum=tree[i].mi=tree[i].mx=a[tim[l]];
return ;
}
int mid=half;
build(Lson);
build(Rson);
pushup(myself);
}
void update(int i,int l,int r,int x,int val)//单点更新
{
if(l==r)
{
tree[i].sum=tree[i].mi=tree[i].mx=val;
return;
}
int mid=half;
pushdown(myself);
if(x<=mid) update(Lson,x,val);
else update(Rson,x,val);
pushup(myself);
}
void update1(int i,int l,int r,int ql,int qr)//区间取反
{
if(ql>qr) return;
if(ql<=l&&qr>=r)
{
tree[i].sum=-tree[i].sum;
lazy[i]=1-lazy[i];
int x=tree[i].mi;
tree[i].mi=-tree[i].mx;
tree[i].mx=-x;
return;
}
pushdown(myself);
int mid=half;
if(qr<=mid) update1(Lson,ql,qr);
else if(ql>mid) update1(Rson,ql,qr);
else update1(Lson,ql,mid),update1(Rson,mid+1,qr);
pushup(myself);
}
int find_sum(int i,int l,int r,int ql,int qr)
{
if(ql>qr) return 0;
if(ql<=l&&qr>=r) return tree[i].sum;
pushdown(myself);
int mid=half;
if(qr<=mid) return find_sum(Lson,ql,qr);
else if(ql>mid) return find_sum(Rson,ql,qr);
else return find_sum(Lson,ql,mid)+find_sum(Rson,mid+1,qr);
}
int find_max(int i,int l,int r,int ql,int qr)
{
if(ql>qr) return -inff;
if(ql<=l&&qr>=r) return tree[i].mx;
pushdown(myself);
int mid=half;
if(qr<=mid) return find_max(Lson,ql,qr);
else if(ql>mid) return find_max(Rson,ql,qr);
else return max(find_max(Lson,ql,mid),find_max(Rson,mid+1,qr));
}
int find_min(int i,int l,int r,int ql,int qr)
{
if(ql>qr) return inff;
if(ql<=l&&qr>=r) return tree[i].mi;
pushdown(myself);
int mid=half;
if(qr<=mid) return find_min(Lson,ql,qr);
else if(ql>mid) return find_min(Rson,ql,qr);
else return min(find_min(Lson,ql,mid),find_min(Rson,mid+1,qr));
}
void solve(int x,int y)//区间更新pre处理
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
update1(1,1,n,dfn[top[x]],dfn[x]);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
update1(1,1,t,dfn[x]+1,dfn[y]);
}
int get_max(int x,int y)
{
int ans=-inff;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=max(ans,find_max(1,1,t,dfn[top[x]],dfn[x]));
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans=max(ans,find_max(1,1,t,dfn[x]+1,dfn[y]));
return ans;
}
int get_min(int x,int y)
{
int ans=inff;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=min(ans,find_min(1,1,t,dfn[top[x]],dfn[x]));
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans=min(ans,find_min(1,1,t,dfn[x]+1,dfn[y]));
return ans;
}
int get_sum(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
ans+=find_sum(1,1,t,dfn[top[x]],dfn[x]);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans+=find_sum(1,1,t,dfn[x]+1,dfn[y]);
return ans;
}
int main()
{
// freopen("E://2.in","r",stdin);
// freopen("E://1.out","w",stdout);
cin>>n;
int x,y,val;
init();
for(int i=1;i<n;i++)
{
scanf("%d %d %d",&x,&y,&val);
x++,y++;
add(x,y,val),add(y,x,val);
}
dfs1(1,1,1);dfs2(1,1);build(1,1,n);
int r;cin>>r;
while(r--)
{
scanf("%s",s);
scanf("%d %d",&x,&y);
x++,y++;
if(s[0]=='C') update(1,1,n,dfn[x],y-1);
else if(s[0]=='N') solve(x,y);
else if(s[2]=='M') printf("%d\n",get_sum(x,y));
else if(s[2]=='X') printf("%d\n",get_max(x,y));
else printf("%d\n",get_min(x,y));
}
return 0;
}
边栏推荐
猜你喜欢
随机推荐
半导体新能源智能装备整机软件系统方案设计
MUV LUV EXTRA 2019CCPC Qinhuangdao Station J Question KMP
神经网络优化器
tianqf的解题思路
分布式理论
更改Jupyter Notebook默认打开目录
买口罩(0-1背包)
排序第一节——插入排序(直接插入排序+希尔排序)(视频讲解26分钟)
car-price-deeplearning-0411
XxlJobConfig distributed timer task management XxlJob configuration class, replace
975. 奇偶跳 有序集合
The water problem of leetcode
力扣208,实现Trie(前缀树)
SIGINT, SIGKILL, SIGTERM signal difference, summary of various signals
MySQL高级特性之分布式(XA)事务的介绍
stm32定时器之简单封装
查看日志常用命令
The working principle of the transformer (illustration, schematic explanation, understand at a glance)
【Docker】Docker安装MySQL
高项 03 项目立项管理