4353: Play with tree
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 31 Solved: 19
[Submit][Status][Discuss]
Description
给你一棵包含N个节点的树，设每条边一开始的边权为0，现在有两种操作：
1）给出参数U,V,C，表示把U与V之间的路径上的边权变成C（保证C≥0）
2）给出参数U,V,C，表示把U与V之间的路径上的边权加上C。但是如果U至V之间路径某条边的边权加上C小于0，那么C=这条边的边权的相反数。
你需要统计出每次一操作过后树中边权为0的边有多少条。
Input
第一行两个整数N,M，分别表示表示节点个数与操作数。
接下来N-1行每行两个整数X,Y表示X,Y之间有一条边。
接下来M行每行4个整数P,U,V,C，P表示操作类型，U,V,C的意义见题目描述。
Output
输出文件包括M行，每行一个整数，表示边权为0的边的个数。
Sample Input
5 4
1 2
1 3
2 4
2 5
1 4 5 1
2 5 3 1
2 5 1 -2
1 4 3 0
1 2
1 3
2 4
2 5
1 4 5 1
2 5 3 1
2 5 1 -2
1 4 3 0
Sample Output
2
0
1
3
0
1
3
HINT
N, M≤100,000
Source
Solution
就是两个操作：1.树链覆盖C 2.树链+C，如果有边+C<0 则C=-minx
随便链剖一下+线段树维护一下就可以了
维护最小值minx，最小值个数minn
覆盖的时候直接覆盖，+C的时候先查询minx再看看是否修改C，然后+C...输出答案就是，如果minx=0，ans+=minn....
边权的树链剖分，就是把边权下放至点权
边<u,v>的值，由u，v中较深的点保存，这样显然除了root每条边和每个点是一一对应的.
这里查询所有边的值，因为默认1为root，所以直接查询[2,N]的就可以了。修改的时候稍微做一下修改就可以了
所以说随便写写就A了.
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<''||ch>'') {if(ch=='-') f=-; ch=getchar();}
while (ch>=''&&ch<='') {x=*x+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 100010
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int N,M;
#define INF 0x7fffffff
namespace SegmentTree
{
struct SegmentTreeNode{int l,r,size,minx,minn,tag,del;}tree[MAXN<<];
#define ls now<<1
#define rs now<<1|1
inline void Update(int now)
{
tree[now].minx=min(tree[ls].minx,tree[rs].minx);
tree[now].minn=tree[ls].minx<tree[rs].minx? tree[ls].minn:tree[rs].minn;
if (tree[ls].minx==tree[rs].minx) tree[now].minx=tree[ls].minx,tree[now].minn=tree[ls].minn+tree[rs].minn;
}
inline void PushDown(int now)
{
if (tree[now].del!=-)
{
tree[ls].minx=tree[now].del; tree[ls].minn=tree[ls].size; tree[ls].del=tree[now].del; tree[ls].tag=;
tree[rs].minx=tree[now].del; tree[rs].minn=tree[rs].size; tree[rs].del=tree[now].del; tree[rs].tag=;
tree[now].del=-;
}
if (tree[now].tag)
{
tree[ls].minx+=tree[now].tag; tree[ls].tag+=tree[now].tag;
tree[rs].minx+=tree[now].tag; tree[rs].tag+=tree[now].tag;
tree[now].tag=;
}
}
inline void BuildTree(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r,tree[now].size=r-l+;
tree[now].del=-; tree[now].tag=;
if (l==r) {tree[now].minn=; tree[now].minx=; return;}
int mid=(l+r)>>;
BuildTree(ls,l,mid);
BuildTree(rs,mid+,r);
Update(now);
}
inline void Change(int now,int L,int R,int C)
{
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) {tree[now].tag+=C; tree[now].minx+=C; return;}
PushDown(now);
int mid=(l+r)>>;
if (L<=mid) Change(ls,L,R,C);
if (R>mid) Change(rs,L,R,C);
Update(now);
}
inline void Modify(int now,int L,int R,int C)
{
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) {tree[now].del=C; tree[now].tag=; tree[now].minx=C; tree[now].minn=tree[now].size; return;}
PushDown(now);
int mid=(l+r)>>;
if (L<=mid) Modify(ls,L,R,C);
if (R>mid) Modify(rs,L,R,C);
Update(now);
}
inline int Getmin(int now,int L,int R)
{
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) return tree[now].minx;
PushDown(now);
int mid=(l+r)>>,re=INF;
if (L<=mid) re=min(re,Getmin(ls,L,R));
if (R>mid) re=min(re,Getmin(rs,L,R));
return re;
}
inline int Query(int now,int L,int R)
{
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) return tree[now].minx==? tree[now].minn:;
PushDown(now);
int mid=(l+r)>>,re=;
if (L<=mid) re+=Query(ls,L,R);
if (R>mid) re+=Query(rs,L,R);
return re;
}
}
namespace ChainPartition
{
int size[MAXN],fa[MAXN],deep[MAXN],top[MAXN],pl[MAXN],pr[MAXN],pre[MAXN],dfn,son[MAXN];
void DFS_1(int now)
{
size[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=fa[now])
{
deep[edge[i].to]=deep[now]+;
fa[edge[i].to]=now;
DFS_1(edge[i].to);
size[now]+=size[edge[i].to];
if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to;
}
}
void DFS_2(int now,int chain)
{
top[now]=chain; pl[now]=++dfn; pre[dfn]=now;
if (son[now]) DFS_2(son[now],chain);
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=fa[now] && edge[i].to!=son[now])
DFS_2(edge[i].to,edge[i].to);
pr[now]=dfn;
}
inline int Get(int x,int y)
{
int re=INF;
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
re=min(re,SegmentTree::Getmin(,pl[top[x]],pl[x]));
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
if (x!=y) re=min(re,SegmentTree::Getmin(,pl[x]+,pl[y]));
return re;
}
inline void Change(int x,int y,int C)
{
int minx=Get(x,y);
if (minx+C<) C=-minx;
// printf("Change %d %d %d\n",x,y,C);
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
SegmentTree::Change(,pl[top[x]],pl[x],C);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
if (x!=y) SegmentTree::Change(,pl[x]+,pl[y],C);
printf("%d\n",SegmentTree::Query(,,N));
}
inline void Modify(int x,int y,int C)
{
// printf("Modify %d %d %d\n",x,y,C);
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
SegmentTree::Modify(,pl[top[x]],pl[x],C);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
if (x!=y) SegmentTree::Modify(,pl[x]+,pl[y],C);
printf("%d\n",SegmentTree::Query(,,N));
}
}
int main()
{
N=read(),M=read();
for (int x,y,i=; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
ChainPartition::DFS_1(); ChainPartition::DFS_2(,);
SegmentTree::BuildTree(,,N);
while (M--)
{
int opt=read(),u=read(),v=read(),C=read();
switch (opt)
{
case : ChainPartition::Modify(u,v,C); break;
case : ChainPartition::Change(u,v,C); break;
}
}
return ;
}
以前看蛋蛋写了好几天....还找Claris要代码.....
1h左右就A了....不过无故弄了个本题第一个RE
ShallWe:"这不是傻逼题么？"