这题在线段树中需要成段覆盖和成段加，在处理时需要当心。 同时需要将边权转换成点权。
题目：毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有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之间树枝上毛毛果个数最多有多少个。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 |
#include<iostream> #include<cstdio> using namespace std; int n,tot,lable,root,f[100100],lazy1[800800],lazy2[800800],a[800800],Next[200010],head[200100],tree[200100],val[200100]; int Number[200100],dep[100100],fa[100100],size[100100],son[100100],bian[100100],tid[100100],top[100100],num[100100]; bool visit[100100]; int Max(int x,int y){ return (x>y)?x:y;} void up(int x) {a[x]=Max(a[x*2],a[x*2+1]);} int swap(int &x,int &y) {int t=x;x=y;y=t;} void down(int x) { if (lazy1[x]!=-1) { lazy1[x*2]=lazy1[x*2+1]=lazy1[x]; a[x*2]=a[x*2+1]=lazy1[x]; lazy2[x*2]=lazy2[x*2+1]=0; lazy1[x]=-1; } if (lazy2[x]!=0) { lazy2[x*2]+=lazy2[x]; lazy2[x*2+1]+=lazy2[x]; a[x*2]+=lazy2[x]; a[x*2+1]+=lazy2[x]; lazy2[x]=0; } } void add(int x,int y,int z,int number) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; Number[tot]=number; } void dfs1(int x,int depth,int father) { dep[x]=depth;fa[x]=father;size[x]=1; visit[x]=true;son[x]=0; int maxsize=0; for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) { f[tree[i]]=val[i];bian[Number[i]]=tree[i]; dfs1(tree[i],depth+1,x); size[x]+=size[tree[i]]; if (size[tree[i]]>maxsize) maxsize=size[tree[i]],son[x]=tree[i]; } } void dfs2(int x,int ancestor) { visit[x]=true; lable++;tid[x]=lable;num[lable]=x;top[x]=ancestor; if (son[x]!=0) dfs2(son[x],ancestor); for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) dfs2(tree[i],tree[i]); } void build(int l,int r,int id) { lazy1[id]=-1;lazy2[id]=0; if (l==r) { a[id]=f[num[l]]; return; } int mid=(l+r)/2; build(l,mid,id*2); build(mid+1,r,id*2+1); up(id); } int query(int x,int y,int l,int r,int id) { if (l>y||r<x||x>y) return -1<<29; if (x<=l&&r<=y) return a[id]; int mid=(l+r)/2; down(id); return Max(query(x,y,l,mid,id*2),query(x,y,mid+1,r,id*2+1)); } void cover(int x,int y,int l,int r,int id,int d) { if (l>y||r<x||x>y) return; if (x<=l&&r<=y) { lazy1[id]=d; lazy2[id]=0; a[id]=d; return; } int mid=(l+r)/2; down(id); cover(x,y,l,mid,id*2,d); cover(x,y,mid+1,r,id*2+1,d); up(id); } void change(int x,int y,int l,int r,int id,int d) { if (l>y||r<x||x>y) return; if (x<=l&&r<=y) { //down(id); if (lazy1[id]!=-1) lazy1[id]+=d;else lazy2[id]+=d; a[id]+=d; return; } int mid=(l+r)/2; down(id); change(x,y,l,mid,id*2,d); change(x,y,mid+1,r,id*2+1,d); up(id); } int Query(int x,int y) { int ans=-1<<30; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=Max(ans,query(tid[top[x]],tid[x],1,n,1)); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans=Max(ans,query(tid[x]+1,tid[y],1,n,1)); return ans; } void Cover(int x,int y,int d) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); cover(tid[top[x]],tid[x],1,n,1,d); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); cover(tid[x]+1,tid[y],1,n,1,d); } void Add(int x,int y,int d) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); change(tid[top[x]],tid[x],1,n,1,d); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); change(tid[x]+1,tid[y],1,n,1,d); } int main() { scanf("%d",&n); tot=lable=0; for (int i=1;i<=n-1;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z,i);add(y,x,z,i); } root=1; f[root]=-1<<30; for (int i=1;i<=n;i++) visit[i]=false; dfs1(1,1,0); for (int i=1;i<=n;i++) visit[i]=false; dfs2(1,1); build(1,n,1); char s[100]; while (true) { scanf("%s",s); if (s[0]=='S') break; int x,y; scanf("%d%d",&x,&y); if (s[0]=='M') { printf("%d\n",Query(x,y)); continue; } if (s[0]=='C'&&s[1]=='h') { cover(tid[bian[x]],tid[bian[x]],1,n,1,y); continue; } int z; scanf("%d",&z); if (s[0]=='C') Cover(x,y,z); if (s[0]=='A') Add(x,y,z); } return 0; } |
