題目鏈接

Solution

樹上差分+線段樹合并.
在每個節點上維護一棵權值線段樹.
然后如果需要修改 \(x,y\) 兩點,則在 \(x\) 處和 \(y\) 處分別加上 \(1\) 的權值.
然后在 \(lca(x,y)\) 以及 \(fa[lca(x,y)]\) 處減掉 \(1\) .
最后面 \(dfs\) 從下往上更新.

由于每一次維護只維護四個點的值,且每次在每一棵樹上也只會修改一條鏈的值.
每次操作時間復雜度和空間復雜度均為 \(O(4*logn)\) .
所以整體時間和空間復雜度即為 \(O(4*nlogn)\) .可以過.

Code

#include<bits/stdc++.h> #define N 100008 #define in(x) x=read() using namespace std; struct sj{int to,next;}a[N*2]; int head[N*2],size,n,q; int dep[N*2],fa[N*2][20],v[N*2]; int T[N*2],L[N*60],R[N*60],rans[N*2]; int num[N*60],rt,tot,m,Ans[N*60],ans[N*60];int read() {char ch=getchar(); int f=1,w=0;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}return f*w; }void add(int x,int y) {a[++size].to=y;a[size].next=head[x];head[x]=size; }void dfs(int x,int fr) {for(int i=head[x];i;i=a[i].next){int tt=a[i].to;if(tt==fr)continue;dep[tt]=dep[x]+1;fa[tt][0]=x;dfs(tt,x);} }int lca(int x,int y) {if(dep[x]<dep[y])swap(x,y);for(int i=19;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];if(x==y) return x;for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0]; }void pushup(int node) {if(ans[L[node]]>=ans[R[node]])ans[node]=ans[L[node]],Ans[node]=Ans[L[node]];else ans[node]=ans[R[node]],Ans[node]=Ans[R[node]]; } void update(int &node,int l,int r,int pos,int v) {if(!node) node=++tot;if(l==r) {ans[node]+=v;Ans[node]=l;return;}int mid=(l+r)/2;if(pos<=mid) update(L[node],l,mid,pos,v);else update(R[node],mid+1,r,pos,v);if(l!=r)pushup(node); } int merge(int x,int y,int l,int r) {if(l==r&&x&&y) ans[x]+=ans[y];if(!x||!y) return x+y;int mid=(l+r)/2;L[x]=merge(L[x],L[y],l,mid);R[x]=merge(R[x],R[y],mid+1,r);if(l!=r)pushup(x);return x; } void Dfs(int x,int fr) {for(int i=head[x];i;i=a[i].next){int tt=a[i].to;if(tt==fr)continue;Dfs(tt,x);T[x]=merge(T[x],T[tt],1,N);}if(ans[T[x]]>0)rans[x]=Ans[T[x]]; }int main() {in(n),in(q);for(int i=1;i<n;i++){int x,y; in(x),in(y);add(x,y),add(y,x);}dep[1]=1; dfs(1,0);for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1]; for(int i=1;i<=q;i++){int x,y,z;in(x),in(y),in(z);int pp=lca(x,y);update(T[x],1,N,z,1);update(T[y],1,N,z,1);update(T[pp],1,N,z,-1);update(T[fa[pp][0]],1,N,z,-1);}Dfs(1,0);for(int i=1;i<=n;i++)printf("%d\n",rans[i]); }

轉載于:https://www.cnblogs.com/Kv-Stalin/p/9773257.html

總結

以上是生活随笔為你收集整理的[Vani有约会]雨天的尾巴 (线段树合并)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。