HDU 5052 树链剖分
题意：给你一棵树，每个点有点权，问从x走到y，先后取两个数a和b，b-a的最大值。
做法：树链剖分一下，然后线段树把路径区间都合并起来。
比赛的时候居然没想出来。。。（现在想想不是很简单嘛。。。）
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 | #include<cstdio>#include<algorithm>using namespace std;const int N=50005;int a[N];int base[N],vec[2*N],pre[2*N],tot;int id[N],rd[N],son[N],deep[N],size[N],fa[N],top[N];int T;int n;void link(int x,int y){ vec[++tot]=y; pre[tot]=base[x]; base[x]=tot;}struct seg{ int ma,mi,fl,fr; seg operator+(const seg &t)const { if (ma==-1) return t; if (t.ma==-1) return *this; int maa=max(ma,t.ma); int mii=min(mi,t.mi); int ffl=max(fl,t.fl); ffl=max(ffl,ma-t.mi); int ffr=max(fr,t.fr); ffr=max(ffr,t.ma-mi); return {maa,mii,ffl,ffr}; } void operator+=(const int t) { ma+=t; mi+=t; }}s[4*N];int lazy[4*N];void build(int i,int l,int r){ lazy[i]=0; if (l==r) { s[i]={a[rd[l]],a[rd[l]],0}; return; } int mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); s[i]=s[i*2]+s[i*2+1];}void pd(int i){ if (lazy[i]) { lazy[i*2]+=lazy[i]; lazy[i*2+1]+=lazy[i]; s[i*2]+=lazy[i]; s[i*2+1]+=lazy[i]; lazy[i]=0; }}void add(int i,int l,int r,int x,int y,int z){ if (x<=l&&r<=y) { s[i]+=z; lazy[i]+=z; return; } pd(i); int mid=(l+r)/2; if (x<=mid) add(i*2,l,mid,x,y,z); if (y>mid) add(i*2+1,mid+1,r,x,y,z); s[i]=s[i*2]+s[i*2+1];}seg get(int i,int l,int r,int x,int y){ if (x<=l&&r<=y) return s[i]; pd(i); int mid=(l+r)/2; seg tmp={-1,-1,-1,-1}; if (x<=mid) tmp=tmp+get(i*2,l,mid,x,y); if (y>mid) tmp=tmp+get(i*2+1,mid+1,r,x,y); return tmp;}void dfs1(int u,int d,int p){ fa[u]=p; deep[u]=d; son[u]=-1; size[u]=1; for (int now=base[u];now;now=pre[now]) { int v=vec[now]; if (v==p) continue; dfs1(v,d+1,u); size[u]+=size[v]; if (son[u]==-1||size[v]>size[son[u]]) son[u]=v; }}void dfs2(int u,int p){ top[u]=p; id[u]=++T; rd[T]=u; if (son[u]!=-1) dfs2(son[u],p); for (int now=base[u];now;now=pre[now]) { int v=vec[now]; if (v==fa[u]||v==son[u]) continue; dfs2(v,v); }}int lca(int x,int y){ int f1=top[x],f2=top[y]; while(f1!=f2) { if (deep[f1]<deep[f2]) swap(f1,f2),swap(x,y); x=fa[f1],f1=top[x]; } if (deep[x]<deep[y]) swap(x,y); return y;}seg getseg(int x,int LCA,int v){ seg tmp={-1,-1,-1,-1}; while(x!=LCA&&deep[top[x]]>deep[LCA]) { tmp=get(1,1,n,id[top[x]],id[x])+tmp; add(1,1,n,id[top[x]],id[x],v); x=fa[top[x]]; } tmp=get(1,1,n,id[LCA],id[x])+tmp; add(1,1,n,id[LCA],id[x],v); return tmp;}int solve(int x,int y,int v){ int LCA=lca(x,y); seg tmp1=getseg(x,LCA,v); add(1,1,n,id[LCA],id[LCA],-v); seg tmp2=getseg(y,LCA,v); int ans=max(tmp1.fl,tmp2.fr); ans=max(ans,tmp2.ma-tmp1.mi); return ans;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); link(x,y); link(y,x); } dfs1(1,1,-1); dfs2(1,-1); build(1,1,n); int q; scanf("%d",&q); while(q--) { int x,y,v; scanf("%d%d%d",&x,&y,&v); printf("%d\n",solve(x,y,v)); } tot=T=0; for (int i=1;i<=n;i++) base[i]=0; }} |
2022年11月09日 03:04
Quality education is a combination of a proper and effective education system. The Indian education department seeks to streamline and provide quality and improved education to all students in the country. Shaala Siddhi data entry The National Programme on School Standards and Evaluation NPSSE ensure the country’s education system is effective and in line with the student’s needs. The NPSSE offers comprehensive and inclusive school evaluation programmes to benefit all students.
2022年12月17日 03:27
FSSAI identified the necessity for an overhaul, which resulted in the creation of a new application called the Food Safety and Compliance System (FoSCoS). During the implementation of FoSCoS, foscos the effort was made to ensure that the majority of its functionality and process flows are as similar to the FLRS program as practicable, while simultaneously making it more user delightful and optimizing its system performance.
2023年2月05日 21:31
BSNL customer care number of each state regarding to BSNL services towards toll free and paid numbers which are accessed from own and other networks across the country. BSNL Customer Care The new digital era based support system contributing a lion’s sharing related to all telecom services, also find the new email address providing BSNL complaint process for payment failed issues for any digital payment service failure related issues like repayment.