BZOJ 3307 雨天的尾巴

Link

总算明白了大神们口中说的“剖完之后套用链上做法”的方法了。。。 # Solution 要对链加标记算前缀和,要想办法转化成序列的问题。然而普通的DFS序可能会把路径弄成很多段,这不好。如果用树链剖分剖出的DFS序,一个路径在DFS序上最多\(O(\log n)\)段,就好了。 # Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include "lucida"
#define alloc(T,c) (T*)malloc((c)*sizeof(T))
using std::lower_bound;
using std::sort;
using std::unique;
using std::vector;
using std::swap;
using std::max;
const int MAXN=100000+11;
int nums[MAXN],nc;
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
struct Edge {
int to;
Edge *pre;
Edge(int to,Edge *pre):to(to),pre(pre){}
void *operator new(size_t) {
static Edge *Me=alloc(Edge,MAXN<<1);
return Me++;
}
}*G[MAXN];
void Adde(int f,int t) {
G[f]=new Edge(t,G[f]);
G[t]=new Edge(f,G[t]);
}
int dep[MAXN],sz[MAXN],prefer[MAXN],fa[MAXN],cht[MAXN];
void DFS(int pos) {
sz[pos]=1;
for(Edge *e=G[pos];e;e=e->pre)
if(fa[pos]!=e->to) {
int u=e->to;
fa[u]=pos;
dep[u]=dep[pos]+1;
DFS(u);
sz[pos]+=sz[u];
if(sz[u]>sz[prefer[pos]])
prefer[pos]=u;
}
}
int dfn[MAXN],dfs[MAXN],dc;
void Assign(int pos) {
dfs[++dc]=pos;
dfn[pos]=dc;
if(prefer[pos]) {
cht[prefer[pos]]=cht[pos];
Assign(prefer[pos]);
for(Edge *e=G[pos];e;e=e->pre)
if(e->to!=prefer[pos] && fa[pos]!=e->to) {
cht[e->to]=e->to;
Assign(e->to);
}
}
}
void Divide() {
DFS(1);
cht[1]=1;
Assign(1);
}
struct Data {
int cnt,id;
Data(int cnt,int id):cnt(cnt),id(id){}
bool operator <(const Data &a) const {
return cnt==a.cnt?id>a.id:cnt<a.cnt;
}
};
struct Tag {
int v,cnt;
Tag(int v,int cnt):v(v),cnt(cnt){}
};
vector<Tag> tag[MAXN];
void Modify(int p1,int p2,int c) {
while(cht[p1]!=cht[p2]) {
if(dep[cht[p1]]<dep[cht[p2]])
swap(p1,p2);
tag[dfn[cht[p1]]].push_back(Tag(c,1));
tag[dfn[p1]+1].push_back(Tag(c,-1));
p1=fa[cht[p1]];
}
if(dep[p1]>dep[p2])
swap(p1,p2);
tag[dfn[p1]].push_back(Tag(c,1));
tag[dfn[p2]+1].push_back(Tag(c,-1));
}
namespace segtree {
struct Node {
Node *son[2];
Data maxv;
Node(Data maxv):maxv(maxv) {
son[0]=son[1]=0;
}
void *operator new(size_t) {
static Node *Me=alloc(Node,MAXN<<2);
return Me++;
}
void Up() {
maxv=max(son[0]->maxv,son[1]->maxv);
}
};
struct SegTree {
Node *root;
int L,R;
Node *operator ->() {
return root;
}
/*
operator Node *() {
return root;
} */
void Build(Node *&pos,int L,int R) {
pos=new Node(Data(0,L));
if(L!=R) {
int Mid=(L+R)>>1;
Build(pos->son[0],L,Mid);
Build(pos->son[1],Mid+1,R);
pos->Up();
}
}
void Edit(Node *pos,int L,int R,int goal,int v) {
if(L==R)
pos->maxv.cnt+=v;
else {
int Mid=(L+R)>>1;
if(goal<=Mid)
Edit(pos->son[0],L,Mid,goal,v);
else
Edit(pos->son[1],Mid+1,R,goal,v);
pos->Up();
}
}
SegTree(int L,int R):L(L),R(R) {
Build(root,L,R);
}
void Edit(int pos,int v) {
Edit(root,L,R,pos,v);
}
};
}using segtree::SegTree;
int main() {
freopen("input","r",stdin);
int n,m;
is>>n>>m;
for(int i=1;i<=n-1;++i) {
int x,y;
is>>x>>y;
Adde(x,y);
}
Divide();
static struct {int p1,p2,c;}op[MAXN];
for(int i=1;i<=m;++i) {
is>>op[i].p1>>op[i].p2>>op[i].c;
nums[++nc]=op[i].c;
}
sort(nums+1,nums+1+nc);
nc=unique(nums+1,nums+1+nc)-nums-1;
for(int i=1;i<=m;++i)
Modify(op[i].p1,op[i].p2,ref(op[i].c));
SegTree seg(1,nc);
static int Ans[MAXN];
for(int i=1;i<=n;++i) {
for(vector<Tag>::iterator it=tag[i].begin();it!=tag[i].end();++it)
seg.Edit(it->v,it->cnt);
Ans[dfs[i]]=nums[seg->maxv.cnt==0?0:seg->maxv.id];
}
for(int i=1;i<=n;++i)
os<<Ans[i]<<'\n';
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利