兄啊你这个码风必没有人来的
by 小粉兔 @ 2020-03-02 02:33:55
惊现兔队！
by Ryo_Yamada @ 2020-03-02 07:41:46
惊现兔队！
~~码风确实毒瘤~~
by USSENTERPRISE @ 2020-03-02 08:15:59
orz 那我重发一份吧QAQ
```
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i <= (b); ++i)
#define drep(i,a,b) for (int i = (a); i >= (b); --i)
#define grep(i,u) for (int i = head[u],v = e[i].v; i; v = e[i = e[i].nxt].v)
#define il inline
#define LL long long
using namespace std;
il int read() {
int res = 0,f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -f;
ch = getchar();
}
while (isdigit(ch)) {
res = (res<<3)+(res<<1)+ch-'0';
ch = getchar();
}
return res*f;
}
namespace qiqi {
const int N = 5e5+5,INF = 0x3f3f3f3f;
int n,m,L,R,ans = -INF,val[N],ecnt,head[N],rt,sum,siz[N],dep[N],col[N],dis[N],mx[N],len[N],fa[N],a[N],q[N],lst[N],now[N],ul[N],uc[N],T;
bool vis[N];
vector<int> vl[N],vc[N];
struct Edge {
int v,c,nxt;
} e[N];
il void add(int u,int v,int c) {
e[++ecnt] = (Edge) {
v,c,head[u]
};
head[u] = ecnt;
}
void getrt(int u,int fa) {
siz[u] = 1;
mx[u] = 0;
grep(i,u) if (v != fa && !vis[v]) {
getrt(v,u);
siz[u] += siz[v];
mx[u] = max(mx[u],siz[v]);
}
mx[u] = max(mx[u],sum-siz[u]);
if (mx[u] < mx[rt]) rt = u;
}
il void calc(int rt) {
int h = 1,t = 0;
++T;
fa[rt] = rt;
grep(i,rt) if (!vis[v]) {
dep[v] = 1;
vl[q[++t]=fa[v]=v].push_back(len[v]=val[col[v]=e[i].c]);
}
while (h <= t) {
int u = q[h++];
if (L <= dep[u] && dep[u] <= R) ans = max(ans,len[u]);
if (dep[u] < R) grep(i,u) if (!vis[v] && !fa[v]) {
dep[v] = dep[u]+1;
fa[v] = fa[u];
col[v] = e[i].c;
len[v] = len[u]+(col[u]!=col[v]?val[col[v]]:0);
q[++t] = v;
if (vl[fa[v]].size() < dep[v]) vl[fa[v]].push_back(len[v]);
else vl[fa[v]][dep[v]-1] = max(vl[fa[v]][dep[v]-1],len[v]);
}
}
drep(i,t,1) {
if (uc[col[fa[q[i]]]] != T) uc[a[++a[0]]=col[fa[q[i]]]] = T;
if (ul[fa[q[i]]] != T) {
ul[fa[q[i]]] = T;
vc[col[fa[q[i]]]].push_back(fa[q[i]]);
}
fa[q[i]] = 0;
}
lst[0] = now[0] = 0;
while (a[0]) {
drep(i,(int)vc[a[a[0]]].size()-1,0) {
int x = vc[a[a[0]]][i],k = vl[x].size();
if (now[0]+k >= L) {
h = 1;
t = 0;
rep(j,max(1,L-k),min(now[0],R-k)) {
while (h <= t && now[j] >= now[q[t]]) --t;
q[++t] = j;
ans = max(ans,now[q[h]]+vl[x][k-1]-val[a[a[0]]]);
}
rep(j,R-k+1,min(now[0],R-1)) {
while (h <= t && now[j] >= now[q[t]]) --t;
q[++t] = j;
while (h <= t && q[h]+R-j < L) ++h;
ans = max(ans,now[q[h]]+vl[x][R-j-1]-val[a[a[0]]]);
}
}
now[0] = k;
rep(j,1,k) now[j] = max(now[j],vl[x][j-1]);
vl[x].clear();
}
if (now[0]+lst[0] >= L) {
h = 1;
t = 0;
rep(i,max(1,L-now[0]),min(lst[0],R-now[0])) {
while (h <= t && lst[i] >= lst[q[t]]) --t;
q[++t] = i;
ans = max(ans,lst[q[h]]+now[now[0]]);
}
rep(i,R-now[0]+1,lst[0]) {
while (h <= t && lst[i] >= lst[q[t]]) --t;
q[++t] = i;
while (h <= t && q[h]+R-i < L) ++h;
ans = max(ans,lst[q[h]]+now[R-i]);
}
}
lst[0] = now[0];
now[0] = 0;
rep(i,1,lst[0]) {
lst[i] = max(lst[i],now[i]);
now[i] = -INF;
}
vc[a[a[0]]].clear();
--a[0];
}
rep(i,1,lst[0]) lst[i] = -INF;
}
void solve(int u) {
vis[u] = 1;
calc(u);
grep(i,u) if (!vis[v]) {
mx[rt = 0] = sum = siz[v];
getrt(v,0);
solve(rt);
}
}
void main() {
int a,b,c;
n = read();
m = read();
L = read();
R = read();
rep(i,1,m) val[i] = read();
rep(i,1,n) lst[i] = now[i] = -INF;
rep(i,1,n-1) {
a = read();
b = read();
c = read();
add(a,b,c);
add(b,a,c);
}
mx[rt = 0] = sum = n;
getrt(1,0);
solve(rt);
printf("%d\n",ans);
}
}
int main() {
qiqi::main();
return 0;
}
```
by jeffqi @ 2020-03-02 11:43:20
A了A了 我是SB QAQ
by jeffqi @ 2020-03-02 13:05:53