当前位置： 移动技术网 > IT编程>开发语言>JavaScript > daklqw 的 T3（点分树上数据结构优化DP）

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

2020年07月15日  | 移动技术网IT编程  | 我要评论

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

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

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

AC Code\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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网