题目大意：给定一棵树，有
m
个操作，每次给一条路径上的每个点分发一个颜色为
z
的物品，所有操作结束后输出每个点上数量最多的是哪种物品
对于每个操作，我们在
x
和
y
上各打上一个插入
z
的标记，然后在
LCA(x,y)
和
Fa(LCA(x,y))
上各打上一个删除
z
的标记
然后我们对
z
维护线段树
DFS一遍，对于每个节点进行如下操作：
1.将所有子节点的线段树合并过来
2.处理标记，该插♂入的插♂入，该删除的删除
3.查询最大值作为答案
这样的复杂度是O(mlogm)的
然而跑不过树链剖分什么鬼……是我没离散化的关系？
#include
#include
#include
#include
#include
#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>>1 if(!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); else Modify(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
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
::iterator it; for(it=operations[x].begin();it!=operations[x].end();it++) if(*it>0) Modify(tree[x],1,1000000000,*it,1); else Modify(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