Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 157 Solved: 72
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 Input5 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
2
0
1
3
N, M≤100,000
Source
/**************************************************************
Problem: 4353
User: ictsing
Language: C++
Result: Accepted
Time:6204 ms
Memory:18060 kb
****************************************************************/
//BZOJ4353 Play with tree
#include <iostream>
#include <cstdio>
using namespace std;
const int mt = 100000+5;
int ecnt=0;
int top[mt];
int to[mt<<1],nxt[mt<<1],adj[mt];
int summ[mt<<2],sum0[mt<<2],minn[mt<<2],add[mt<<2],chg[mt<<2];
int fa[mt],val[mt],id[mt],dep[mt],opt[mt],fp[mt],sz[mt];
int tim=0;
int n,m;
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
void adde(int u,int v)
{
ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],adj[u]=ecnt;
}
void dfs1(int u)
{
sz[u]=1,dep[u]=dep[fa[u]]+1;
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(fa[u]==v) continue;
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(sz[v]>sz[opt[u]])
opt[u]=v;
}
}
void dfs2(int u,int chain)
{
top[u]=chain;id[u]=++tim,fp[tim]=u;
if(opt[u]) dfs2(opt[u],chain);
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(v^opt[u]&&v^fa[u])
dfs2(v,v);
}
}
void pushup(int rt)
{
sum0[rt]=sum0[rt<<1]+sum0[rt<<1|1];
if (minn[rt<<1]==minn[rt<<1|1])
{
minn[rt]=minn[rt<<1];
summ[rt]=summ[rt<<1]+summ[rt<<1|1];
}
else if (minn[rt<<1]<minn[rt<<1|1])
{
minn[rt]=minn[rt<<1];
summ[rt]=summ[rt<<1];
}
else
{
minn[rt]=minn[rt<<1|1];
summ[rt]=summ[rt<<1|1];
}
}
void pushdown(int rt,int l,int r)
{
int mid=(l+r)>>1;
if (chg[rt]!=1e9)
{
minn[rt<<1]=chg[rt<<1]=chg[rt];add[rt<<1]=0;
summ[rt<<1]=mid-l+1;
if (!minn[rt<<1]) sum0[rt<<1]=mid-l+1;
else sum0[rt<<1]=0;
minn[rt<<1|1]=chg[rt<<1|1]=chg[rt];add[rt<<1|1]=0;
summ[rt<<1|1]=r-mid;
if (!minn[rt<<1|1]) sum0[rt<<1|1]=r-mid;
else sum0[rt<<1|1]=0;
chg[rt]=1e9;
}
if (add[rt])
{
minn[rt<<1]+=add[rt];minn[rt<<1|1]+=add[rt];
if (!minn[rt<<1]) sum0[rt<<1]=summ[rt<<1];
else sum0[rt<<1]=0;
if (!minn[rt<<1|1]) sum0[rt<<1|1]=summ[rt<<1|1];
else sum0[rt<<1|1]=0;
if (chg[rt<<1]!=1e9) chg[rt<<1]+=add[rt];
else add[rt<<1]+=add[rt];
if (chg[rt<<1|1]!=1e9) chg[rt<<1|1]+=add[rt];
else add[rt<<1|1]+=add[rt];
add[rt]=0;
}
}
void build(int rt,int l,int r)
{
chg[rt]=1e9;
if(l==r)
{
minn[rt]=0;
sum0[rt]=summ[rt]=l-r+1;
if(l==1)
minn[rt]=1e9,sum0[rt]=summ[rt]=0;
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
//cout<<rt<<" "<<chg[rt]<<" "<<minn[rt]<<" "<<sum0[rt]<<" "<<summ[rt]<<" fuck "<<endl;
}
void addd(int rt,int l,int r,int lft,int rgt,int c)
{
if(lft>rgt) return ;
if(lft<=l&&r<=rgt)
{
minn[rt]+=c;
if(!minn[rt]) sum0[rt]=summ[rt];
else sum0[rt]=0;
if(chg[rt]!=1e9) chg[rt]+=c;
else add[rt]+=c;
return ;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if(lft<=mid) addd(rt<<1,l,mid,lft,rgt,c);
if(rgt>mid) addd(rt<<1|1,mid+1,r,lft,rgt,c);
pushup(rt);
}
void change(int rt,int l,int r,int lft,int rgt,int c)
{
if(lft>rgt) return ;
if(lft<=l&&r<=rgt)
{
minn[rt]=c;summ[rt]=r-l+1;
if(c==0) sum0[rt]=r-l+1;
else sum0[rt]=0;
chg[rt]=c,add[rt]=0;
return ;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if(lft<=mid) change(rt<<1,l,mid,lft,rgt,c);
if(rgt>mid) change(rt<<1|1,mid+1,r,lft,rgt,c);
pushup(rt);
}
void lca_chg(int x,int y,int c)
{
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(1,1,n,id[top[x]],id[x],c);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
change(1,1,n,id[y]+1,id[x],c);
}
void lca_addd(int x,int y,int c)
{
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
addd(1,1,n,id[top[x]],id[x],c);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
addd(1,1,n,id[y]+1,id[x],c);
}
int query(int rt,int l,int r,int lft,int rgt)
{
if(lft>rgt) return 1e9;
if(lft<=l&&r<=rgt)
{
return minn[rt];
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
int res=1e9;
if(lft<=mid) res=min(res,query(rt<<1,l,mid,lft,rgt));
if(mid<rgt) res=min(res,query(rt<<1|1,mid+1,r,lft,rgt));
pushup(rt);
return res;
}
int lca_query(int x,int y)
{
int res=1e9;
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=min(res,query(1,1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
res=min(res,query(1,1,n,id[y]+1,id[x]));
return res;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n-1;i++)
{
int x=read(),y=read();
adde(x,y),adde(y,x);
}
dfs1(1);
dfs2(1,1);
build(1,1,n);
while(m--)
{
int op=read(),u=read(),v=read(),c=read();
//cout<<id[u]<<" "<<id[v]<<" "<<endl;
if(op==1)
{
lca_chg(u,v,c);
}
else
{
int mm=lca_query(u,v);
if(mm+c<0) c=-mm;
lca_addd(u,v,c);
}
printf("%d\n",sum0[1]);
}
return 0;
}
评论