Description
N个点，形成一个树状结构。有M次发放，每次选择两个点x,y
对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成
所有发放后，每个点存放最多的是哪种物品。
Input
第一行数字N，M
接下来N-1行，每行两个数字a,b,表示a与b间有一条边
再接下来M行，每行三个数字x,y,z.如题
Output
输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种，如果有
多种物品的数量一样，输出编号最小的。如果某个点没有物品
则输出0
Sample Input
20 50
8 6
10 6
18 6
20 10
7 20
2 18
19 8
1 6
14 20
16 10
13 19
3 14
17 18
11 19
4 11
15 14
5 18
9 10
12 15
11 14 87
12 1 87
14 3 84
17 2 36
6 5 93
17 6 87
10 14 93
5 16 78
6 15 93
15 5 16
11 8 50
17 19 50
5 4 87
15 20 78
1 17 50
20 13 87
7 15 22
16 11 94
19 8 87
18 3 93
13 13 87
2 1 87
2 6 22
5 20 84
10 12 93
18 12 87
16 10 93
8 17 93
14 7 36
7 4 22
5 9 87
13 10 16
20 11 50
9 16 84
10 17 16
19 6 87
12 2 36
20 9 94
9 2 84
14 1 94
5 5 94
8 17 16
12 8 36
20 17 78
12 18 50
16 8 94
2 19 36
10 18 36
14 19 50
4 12 50
Sample Output
87
36
84
22
87
87
22
50
84
87
50
36
87
93
36
94
16
87
50
50
1<=N,M<=100000
1<=a,b,x,y<=N
1<=z<=10^9
题目分析
动态开点权值线段树合并= =
树上差分一下
在x,y处+z lca(x,y)-z fa[lca(x,y)]-z
用动态开点权值线段树来维护每个节点的信息 维护每个节点的线段树中次数最多的(次数相等字典序最小)权值和每个区间的最大size
在打完标记后 从下自上将每个节点和自己的子节点进行线段树合并 顺便维护上述信息即可
改成结构体勉强卡过去 竟然跑不过多一个log的树链剖分真是害怕
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,tot;
int head[100010],to[200010],net[200010];
int fa[100010][23],deep[100010];
inline char get(void)
{
static char buf[1000000], *p1 = buf, *p2 = buf;
if (p1 == p2)
{
p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
inline int read()
{
int x=0; static char c;
for (; !(c >= '0' && c <= '9'); c = get());
for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get());
return x;
}
void add(int x,int y) { net[++tot]=head[x],head[x]=tot,to[tot]=y; }
void dfs(int x)
{
deep[x]=deep[fa[x][0]]+1;
for(int i=1;fa[x][i-1];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=net[i])
if(to[i]!=fa[x][0]) fa[to[i]][0]=x,dfs(to[i]);
}
struct your
{
int lson,rson;
int maxx,size;
}a[6000100];
int root[100010],cnt;
void update(int dx,int l,int r,int c,int &x)
{
if(!x) x=++cnt;
if(l==r)
{
a[x].size+=c,a[x].maxx=l;
return ;
}
int mid=(l+r)>>1;
if(dx<=mid) update(dx,l,mid,c,a[x].lson);
else update(dx,mid+1,r,c,a[x].rson);
if(a[a[x].lson].size>=a[a[x].rson].size)
a[x].size=a[a[x].lson].size,a[x].maxx=a[a[x].lson].maxx;
else a[x].size=a[a[x].rson].size,a[x].maxx=a[a[x].rson].maxx;
}
int getlca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int temp=19;temp>=0;temp--)
if(deep[fa[x][temp]]>=deep[y]) x=fa[x][temp];
if(x==y) return x;
for(int temp=19;temp>=0;temp--)
if(fa[x][temp]!=fa[y][temp])
x=fa[x][temp],y=fa[y][temp];
return fa[x][0];
}
void merge(int &x,int y,int l,int r)
{
if(!x||!y) { x=x+y; return ; }
if(l==r) { a[x].size+=a[y].size; return ; }
int mid=(l+r)>>1;
merge(a[x].lson,a[y].lson,l,mid),merge(a[x].rson,a[y].rson,mid+1,r);
if(a[a[x].lson].size>=a[a[x].rson].size)
a[x].size=a[a[x].lson].size,a[x].maxx=a[a[x].lson].maxx;
else a[x].size=a[a[x].rson].size,a[x].maxx=a[a[x].rson].maxx;
}
int ans[100010];
void dfs2(int x)
{
for(int i=head[x];i;i=net[i])
if(to[i]!=fa[x][0])
dfs2(to[i]),merge(root[x],root[to[i]],1,1e9);
ans[x]=a[root[x]].maxx;
}
int main()
{
scanf("%d%d",&n,&m);
for(int x,y,i=1;i<n;i++)
x=read(),y=read(),add(x,y),add(y,x);
dfs(1);
for(int x,y,z,i=1;i<=m;i++)
{
x=read(),y=read(),z=read();
int lca=getlca(x,y);
update(z,1,1e9,1,root[x]);
update(z,1,1e9,1,root[y]);
update(z,1,1e9,-1,root[lca]);
if(lca!=1) update(z,1,1e9,-1,root[fa[lca][0]]);
}
dfs2(1);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
