daklqw 的 T3（点分树上数据结构优化DP）

设$f_x$为从第$x$个事件开始做最多的收益。
那么这个$dp$是按照时间线从后往前的$dp$，求每个点的做起点的答案可以简单的在每个点初始放一个$A=K=P=0$的时间即可解决。
对于两个事件之间的转移，我们只需要这两个事件
在树上的距离$s1$，
最小多走多少距离可以到达一个奖励边刷分并且走回这两个点的最短路径$s2$，（贪心来说，如果我们绕路，那么一定是在一个最近的奖励边上面刷分）
最短路径上本来有多少奖励边$c$。
那么如果这两个事件之间可以让我们移动的事件有$T$，
分类讨论一下即可得到在完成这两个事件的同时我们最多能刷多少分。

预处理出每个点离最近的奖励边距离之后，
发现上面三个值都是只和这两个事件在树上的路径有关，可以在点分树上维护。
那么一条路径$a\to b$变成了$a\to c \to b$。
要么中途完全不刷分，在$c$上面插入时间点：$a$事件的时间组合上$dis_{a,c}$，价值：$f_a$。
$b$直接在$c$上面用数据结构查。
要么$a\to c$中刷分，要么$c\to b$中刷分。
刷分的话就是对于多余的$2$秒可以换$2c$的分，对于时间点$\bmod 2$分别开两个数据结构维护一下即可。

如果直接上线段树空间是$5n\log ^2n$的，$30000$都过不去。
将所有可能的插入和询问点，离散化后写树状数组，一个询问只会贡献$O(\log n)$个点，所以空间复杂度是$O(n \log n)$的。

$\mathcal AC \ Code$

#include<bits/stdc++.h>
#define maxn 100005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
#define LL long long 
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;

char Start;

char cb[1<<16],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++)
template<class T>void read(T &res){
	char ch;
	for(;!isdigit(ch=getc()););
	for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}
LL C;
int n,Q,T;
int h[maxn],D[maxn],A[maxn],K[maxn],P[maxn],c[maxn];
int info[maxn],Prev[maxn<<1],to[maxn<<1],cst[maxn<<1],cnt_e=1;
void Node(int u,int v,int c){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v,cst[cnt_e]=c; }
bool cmp(const int &u,const int &v){ return A[u] == A[v] ? K[u] > K[v] : A[u] > A[v]; }
#define lim 19
int dep[maxn],fa[lim][maxn],fadis[lim][maxn],faminh[lim][maxn],facst[lim][maxn],sz[maxn];
vector<int>sb[maxn];

void dfs0(int u,int ff,int tsz,int &mn,int &rt){
	int mx = 0;sz[u] = 1;
	for(int i=info[u],v;i;i=Prev[i]) if((v=to[i])^ff && dep[v] == -1){
		dfs0(v,u,tsz,mn,rt);
		sz[u] += sz[v];
		mx = max(mx , sz[v]);
	}
	if((mx = max(mx , tsz - sz[u])) < mn)
		mn = mx , rt = u;
}

int Gert(int u,int tsz){
	int mn = 0x3f3f3f3f , rt = -1;
	dfs0(u,0,tsz,mn,rt);
	return rt;
}

void ser(int u,int ff,int pa,int D,int ndis,int nh,int ncst){
	nh = min(nh , h[u]);sz[u] = 1;
	fa[D][u] = pa , fadis[D][u] = ndis , faminh[D][u] = nh , facst[D][u] = ncst;
	for(int i=info[u],v;i;i=Prev[i]) if(dep[v=to[i]] == -1 && v!= ff)
		ser(v,u,pa,D,ndis+1,nh,ncst+cst[i])  ,sz[u] += sz[v];
}

void Solve(int u,int d){
	dep[u] = d;
	ser(u,0,u,d,0,h[u],0);
	for(int i=info[u],v;i;i=Prev[i]) if(dep[v=to[i]] == -1)
		Solve(Gert(v,sz[v]),d+1);
}

#define maxp maxn * 250
vector<LL>rt[maxn][5];



int fd(vector<int>&s,int tim){
	return lower_bound(s.begin(),s.end(),tim)-s.begin()+1;
}

void ins(vector<LL>&u,int p,LL v){
	for(;p;p-=p&-p) u[p] = max(u[p],v);
}

LL qry(vector<LL>&u,int p){
	LL r=-inf;
	for(;p<u.size();p+=p&-p)
		r = max(r , u[p]);
	return r;
}

void upd(int u,LL val,int tim,int dh){
	if(tim < 0) return;
	ins(rt[u][0],fd(sb[u],tim),val); 
	ins(rt[u][tim&1?4:3],fd(sb[u],tim),val+C*tim);
	if(tim - dh >= 0)
		ins(rt[u][tim-dh&1?2:1],fd(sb[u],tim-dh),val+C*(tim-dh));
}

LL qry2(int u,int tim,int dh){
	if(tim > T) return -inf;
	LL r = qry(rt[u][0],fd(sb[u],tim));
	r = max(r , qry(rt[u][1],fd(sb[u],tim)) - C * tim - ((tim&1) != 0) * C);
	r = max(r , qry(rt[u][2],fd(sb[u],tim)) - C * tim - ((tim&1) != 1) * C);
	if(tim + dh <= T)
		r = max(r , 
			max(
				qry(rt[u][3],fd(sb[u],tim+dh)) - (tim + dh) * C - ((tim&1) != 0) * C ,
				qry(rt[u][4],fd(sb[u],tim+dh)) - (tim + dh) * C - ((tim&1) != 1) * C
			));
	return r;
}

LL qry(int u,int tim){
	LL r = 0;
	if(tim + h[u] / 2 <= T) r = (T - tim - h[u] / 2) * C;
	per(i,dep[u],0)
		r = max(r , qry2(fa[i][u],tim + fadis[i][u],faminh[i][u]) + facst[i][u] * C);
	return r;
}

bool chk(int a){ return 0 <= a && a <= T; }
char End;

int main(){
	
	freopen("daklqw.in","r",stdin);
	freopen("daklqw.out","w",stdout);
	
	cerr<< (&End - &Start) / 1024 / 1024 << endl;
	read(n),read(Q),read(T),read(C);
	memset(h,0x3f,sizeof h);
	memset(dep,-1,sizeof dep);
	rep(i,1,n-1){
		int u,v,w;read(u),read(v),read(w);
		Node(u,v,w),Node(v,u,w);
		if(w) h[u] = h[v] = 0;
	}
	rep(i,1,Q)
		read(D[i]),read(A[i]),read(K[i]),read(P[i]),c[i] = i;
	sort(c+1,c+1+Q,cmp);
	queue<int>q;
	rep(i,1,n) if(!h[i]) q.push(i);
	for(int u;!q.empty();){
		u = q.front() , q.pop();
		for(int i=info[u],v;i;i=Prev[i]) if(h[v=to[i]] > h[u] + 2)
			h[v] = h[u] + 2 , q.push(v);
	}
	Solve(Gert(1,n),0);
	rep(i,1,Q){
		int u = D[i];
		per(j,dep[u],0){
			if(chk(A[i]-fadis[j][u]))
				sb[fa[j][u]].push_back(A[i]-fadis[j][u]);
			if(chk(A[i]-fadis[j][u]-faminh[j][u]))
				sb[fa[j][u]].push_back(A[i]-fadis[j][u]-faminh[j][u]);
			if(chk(A[i]+K[i]+fadis[j][u]))
				sb[fa[j][u]].push_back(A[i]+K[i]+fadis[j][u]);
			if(chk(A[i]+K[i]+fadis[j][u]+faminh[j][u]))
				sb[fa[j][u]].push_back(A[i]+K[i]+fadis[j][u]+faminh[j][u]);
		}
	}
	rep(i,1,n){
		sb[i].push_back(0),
		sort(sb[i].begin(),sb[i].end()),
		sb[i].resize(unique(sb[i].begin(),sb[i].end())-sb[i].begin());
		rep(j,0,4) rt[i][j] = vector<LL>(sb[i].size()+1 , -inf);
	}
	rep(i,1,Q){
		int u = c[i];
		LL f = qry(D[u],A[u]+K[u]) + P[u];
		per(j,dep[D[u]],0) upd(fa[j][D[u]],f+facst[j][D[u]]*C,A[u]-fadis[j][D[u]],faminh[j][D[u]]);
	}
	rep(i,1,n) printf("%lld%c",qry(i,0)," \n"[i==n]);
}

本文地址：https://blog.csdn.net/qq_35950004/article/details/107302341