1984: 月下“毛景树”
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 1282 Solved: 410
[Submit][Status][Discuss]
Description
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： Change k w：将第k条树枝上毛毛果的个数改变为w个。 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问： Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
Input
第一行一个正整数N。 接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。
Output
对于毛毛虫的每个询问操作，输出一个答案。
Sample Input
4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop
Sample Output
9
16
16
【Data Range】
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
HINT
Source
题解：
挺好的一道题。(处理边权的经典题)
其实就是把每条边上的权值放到这条边下方的点上即可。(这里Orz Popoqqq)
然后就是直接树链剖分即可。。。
但是一定要打标记。（两个标记：add和cover标记。）
而且，一定要先处理 覆盖标记 ，再处理 加数标记 。
因为询问时比如到了[l,r]区间，[l,r]区间原来的标记已经被下传过了。（就是如果原来有add标记，我现在要打个cover标记时，原来的add标记就要被清空。）所以询问时先覆盖，再加数。（加数一定是在覆盖后的数上加。）
然后用线段树维护一下即可。。。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
struct node
{
int begin,end,next;
}edge[MAXN*];
struct NODE
{
int left,right,a,c,mx;
}tree[MAXN*];
int cnt,Head[MAXN],pos[MAXN],size[MAXN],deep[MAXN],P[MAXN][],chain[MAXN],belong[MAXN],id[MAXN],vv[MAXN],UU[MAXN],VV[MAXN],WW[MAXN],SIZE,n;
bool vis[MAXN];
void addedge(int bb,int ee)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee)
{
addedge(bb,ee);addedge(ee,bb);
}
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void dfs1(int u)
{
int i,v;
size[u]=;vis[u]=true;
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(vis[v]==false)
{
deep[v]=deep[u]+;
P[v][]=u;
dfs1(v);
size[u]+=size[v];
}
}
}
void Ycl()
{
int i,j;
for(j=;(<<j)<=n;j++)
{
for(i=;i<=n;i++)
{
if(P[i][j-]!=-)P[i][j]=P[P[i][j-]][j-];
}
}
}
void dfs2(int u,int chain)
{
int k=,i,v;
pos[u]=++SIZE;belong[u]=chain;
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(deep[v]>deep[u]&&size[v]>size[k])k=v;
}
if(k==)return;
dfs2(k,chain);
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(deep[v]>deep[u]&&v!=k)dfs2(v,v);
}
}
int LCA(int x,int y)
{
int i,j;
if(deep[x]<deep[y])swap(x,y);
for(i=;(<<i)<=deep[x];i++);i--;
for(j=i;j>=;j--)if(deep[x]-(<<j)>=deep[y])x=P[x][j];
if(x==y)return x;
for(j=i;j>=;j--)
{
if(P[x][j]!=-&&P[x][j]!=P[y][j])
{
x=P[x][j];
y=P[y][j];
}
}
return P[x][];
}
void Pushup(int k)
{
tree[k].mx=max(tree[k*].mx,tree[k*+].mx);
}
void Update1(int k,int k1)
{
tree[k].mx=k1;tree[k].a=;tree[k].c=k1;
}
void Update2(int k,int k1)
{
tree[k].a+=k1;tree[k].mx+=k1;
}
void Pushdown(int k)
{
int l=k*,r=k*+;
if(tree[k].c!=-)
{
Update1(l,tree[k].c);Update1(r,tree[k].c);
tree[k].c=-;
}
if(tree[k].a!=)
{
Update2(l,tree[k].a);Update2(r,tree[k].a);
tree[k].a=;
}
}
void Build(int k,int l,int r)
{
tree[k].left=l;tree[k].right=r;tree[k].c=-;tree[k].a=;
if(l==r){tree[k].mx=vv[l];return;}
int mid=(l+r)/;
Build(k*,l,mid);Build(k*+,mid+,r);
Pushup(k);
}
int Query_max(int k,int l,int r)
{
if(l<=tree[k].left&&tree[k].right<=r)return tree[k].mx;
Pushdown(k);
int mid=(tree[k].left+tree[k].right)/;
if(r<=mid)return Query_max(k*,l,r);
else if(l>mid)return Query_max(k*+,l,r);
else return max(Query_max(k*,l,mid),Query_max(k*+,mid+,r));
}
void Add(int k,int l,int r,int A)
{
if(l<=tree[k].left&&tree[k].right<=r){tree[k].a+=A;tree[k].mx+=A;return;}
Pushdown(k);
int mid=(tree[k].left+tree[k].right)/;
if(r<=mid)Add(k*,l,r,A);
else if(l>mid)Add(k*+,l,r,A);
else {Add(k*,l,mid,A);Add(k*+,mid+,r,A);}
Pushup(k);
}
void Cover(int k,int l,int r,int C)
{
if(l<=tree[k].left&&tree[k].right<=r){tree[k].c=C;tree[k].a=;tree[k].mx=C;return;}
Pushdown(k);
int mid=(tree[k].left+tree[k].right)/;
if(r<=mid)Cover(k*,l,r,C);
else if(l>mid)Cover(k*+,l,r,C);
else {Cover(k*,l,mid,C);Cover(k*+,mid+,r,C);}
Pushup(k);
}
int Solve_max(int x,int f)
{
int MAX=-INF;
while(belong[x]!=belong[f])
{
MAX=max(MAX,Query_max(,pos[belong[x]],pos[x]));
x=P[belong[x]][];
}
if(f!=x)MAX=max(MAX,Query_max(,pos[f]+,pos[x]));
return MAX;
}
void Solve_add(int x,int f,int add)
{
while(belong[x]!=belong[f])
{
Add(,pos[belong[x]],pos[x],add);
x=P[belong[x]][];
}
if(x!=f)Add(,pos[f]+,pos[x],add);
}
void Solve_cover(int x,int f,int cover)
{
while(belong[x]!=belong[f])
{
Cover(,pos[belong[x]],pos[x],cover);
x=P[belong[x]][];
}
if(x!=f)Cover(,pos[f]+,pos[x],cover);
}
int main()
{
int i,U,V,W,lca,k;
char zs[];
n=read();
memset(Head,-,sizeof(Head));cnt=;
for(i=;i<n;i++){UU[i]=read(),VV[i]=read(),WW[i]=read();addedge1(UU[i],VV[i]);}
memset(P,-,sizeof(P));SIZE=;
dfs1();Ycl();
dfs2(,);
memset(id,,sizeof(id));
for(i=;i<n;i++)//存储每条边下方的点.
{
if(deep[UU[i]]>deep[VV[i]])id[i]=UU[i];
else id[i]=VV[i];
}
for(i=;i<n;i++)vv[pos[id[i]]]=WW[i];
Build(,,n);
while()
{
scanf("\n%s",zs);
if(zs[]=='S')break;
if(zs[]=='M')
{
U=read();V=read();
lca=LCA(U,V);
printf("%d\n",max(Solve_max(U,lca),Solve_max(V,lca)));
}
else if(zs[]=='A')
{
U=read();V=read();W=read();
lca=LCA(U,V);
Solve_add(U,lca,W);Solve_add(V,lca,W);
}
else
{
if(zs[]=='o')
{
U=read();V=read();W=read();
lca=LCA(U,V);
Solve_cover(U,lca,W);Solve_cover(V,lca,W);
}
else
{
k=read();W=read();
vv[pos[id[k]]]=W;
Cover(,pos[id[k]],pos[id[k]],W);
}
}
}
return ;
}