BZOJ 3307 雨天的尾巴 线段树

线段树"/>

BZOJ 3307 雨天的尾巴 线段树

题目大意：给定一棵树，有 m $m$个操作，每次给一条路径上的每个点分发一个颜色为z$z$的物品，所有操作结束后输出每个点上数量最多的是哪种物品
对于每个操作，我们在 x $x$和y$y$上各打上一个插入 z $z$的标记，然后在LCA(x,y)$LCA(x,y)$和 Fa(LCA(x,y)) $Fa(LCA(x,y))$上各打上一个删除 z $z$的标记
然后我们对z$z$维护线段树
DFS一遍，对于每个节点进行如下操作：
1.将所有子节点的线段树合并过来
2.处理标记，该插♂入的插♂入，该删除的删除
3.查询最大值作为答案
这样的复杂度是O(mlogm)的
然而跑不过树链剖分什么鬼……是我没离散化的关系？

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 100100
using namespace std;struct Segtree{Segtree *ls,*rs;int pos,val;void* operator new (size_t){static Segtree *mempool,*C;if(C==mempool)mempool=(C=new Segtree[1<<15])+(1<<15);C->ls=C->rs=0x0;C->pos=0;C->val=0;return C++;}void Push_Up(){val=0;if(ls&&ls->val>val)val=ls->val,pos=ls->pos;if(rs&&rs->val>val)val=rs->val,pos=rs->pos;}friend void Modify(Segtree *&p,int x,int y,int pos,int val){int mid=x+y>>1if(!p) p=new Segtree;if(x==y){p->pos=mid;p->val+=val;if(!p->val)p=0x0;return ;}if(pos<=mid)Modify(p->ls,x,mid,pos,val);elseModify(p->rs,mid+1,y,pos,val);p->Push_Up();if(!p->val)p=0x0;}friend void Merge(Segtree *&p1,Segtree *p2,int x,int y){int mid=x+y>>1;if(!p2) return ;if(!p1){p1=p2;return ;}if(x==y){p1->val+=p2->val;return ;}Merge(p1->ls,p2->ls,x,mid);Merge(p1->rs,p2->rs,mid+1,y);p1->Push_Up();}
}*tree[M];struct abcd{int to,next;
}table[M<<1];int n,m;
int dpt[M],fa[M][17],ans[M];vector<int> operations;void Add(int x,int y)
{table[++tot].to=y;table[tot].next=head[x];head[x]=tot;
}void DFS1(int x)
{int i,j;dpt[x]=dpt[fa[x][0]]+1;for(j=1;j<=16;j++)fa[i][j]=fa[fa[i][j-1]][j-1];for(i=head[x];i;i=table[i].next)if(table[i].to!=fa[x])fa[table[i].to][0]=x,DFS1(table[i].to);
}int LCA(int x,int y)
{int j;for(j=16;~j;j--)if(dpt[fa[x][j]]>=dpt[y])x=fa[x][j];if(x==y) return x;for(j=16;~j;j--)if(fa[x][j]!=fa[y][j])x=fa[x][j],y=fa[y][j];return fa[x][0];
}void DFS2(int x)
{int i;for(i=head[x];i;i=table[i].next)if(table[i].to!=fa[x][0]){DFS2(table[i].to);Merge(tree[x],tree[table[i].to]);}vector<int>::iterator it;for(it=operations[x].begin();it!=operations[x].end();it++)if(*it>0)Modify(tree[x],1,1000000000,*it,1);elseModify(tree[x],1,1000000000,-*it,-1);if(tree[x])ans[x]=tree[x]->pos;
}int main()
{int i,x,y,z;cin>>n>>m;for(i=1;i<n;i++){scanf("%d%d",&x,&y);Add(x,y);Add(y,x);}DFS1(1);for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);int lca=LCA(x,y);operations[x].push_back(z);operations[y].push_back(z);operations[lca].push_back(-z);operations[fa[lca][0]].push_back(-z);}DFS2(1);for(i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}