洛谷 - P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并(树上差分+线段树合并)

题目链接：点击查看

题目大意：给出一棵树，再给出 m 次操作，每次操作会选择两个点 ( x , y ) ，使得这条路径上的所有点的种类 z 加一，最后问每个点的哪个种类出现的频率最高，若多个种类出现频率相同时，输出编号最小的

题目分析：线段树合并模板题，感觉 update 函数和主席树非常像，所以就仿照主席树的写法去实现的，相比于正常的线段树来说，仅仅多了一个 merge 函数用于合并两棵线段树罢了，时间复杂度是严格 nlogn 的，因为维护的时候采用的是树上差分，即：

x + 1

y + 1

lca( x , y ) - 1

fa[ lca( x , y ) ] -1

对于某次操作共需要维护 4 条链，也就是说总共需要维护 4 * m * logn 条链，所以空间需要开 50 倍才够，对于这个题目而言，在每个节点上都维护一棵线段树然后 dfs 合并即可

代码：
 

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>node[N];int ans[N];int dp[N][20],deep[N];void dfs(int u,int fa,int dep) {deep[u]=dep;dp[u][0]=fa;for(int i=1;i<20;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(auto v:node[u]){if(v==fa)continue;dfs(v,u,dep+1);} }int LCA(int x,int y) {if(deep[x]<deep[y])swap(x,y);for(int i=19;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=19;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0]; }struct Node {int l,r,mmax,id; }tree[N*50];int root[N],tot;void pushup(int k) {if(tree[tree[k].l].mmax>=tree[tree[k].r].mmax){tree[k].mmax=tree[tree[k].l].mmax;tree[k].id=tree[tree[k].l].id;}else{tree[k].mmax=tree[tree[k].r].mmax;tree[k].id=tree[tree[k].r].id;} }void update(int& k,int pos,int val,int l,int r) {if(!k)k=++tot;assert(tot<N*50);if(l==r){tree[k].mmax+=val;tree[k].id=l;return;}int mid=l+r>>1;if(pos<=mid)update(tree[k].l,pos,val,l,mid);elseupdate(tree[k].r,pos,val,mid+1,r);pushup(k); }void merge(int& a,int b,int l,int r) {if(!a||!b){a=a+b;return;}if(l==r){tree[a].mmax+=tree[b].mmax;tree[a].id=l;return;}int mid=l+r>>1;merge(tree[a].l,tree[b].l,l,mid);merge(tree[a].r,tree[b].r,mid+1,r);pushup(a); }void dfs_ans(int u,int fa) {for(auto v:node[u]){if(v==fa)continue;dfs_ans(v,u);merge(root[u],root[v],1,100000);}if(tree[root[u]].mmax)ans[u]=tree[root[u]].id; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}dfs(1,0,0);while(m--){int x,y,z;scanf("%d%d%d",&x,&y,&z);int lca=LCA(x,y); update(root[x],z,1,1,100000);update(root[y],z,1,1,100000);update(root[lca],z,-1,1,100000);update(root[dp[lca][0]],z,-1,1,100000);}dfs_ans(1,0);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0; }

 

总结

以上是生活随笔为你收集整理的洛谷 - P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并(树上差分+线段树合并)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。