QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308135#5439. Meet in the Middlexx019TL 0ms0kbC++204.1kb2024-01-19 16:27:582024-01-19 16:27:58

Judging History

你现在查看的是最新测评结果

  • [2024-01-19 16:27:58]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-01-19 16:27:58]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
const int inf=1e18,mod=998244353;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct edge{
	int v,w,nxt;
};
struct Graph{
	int tot,head[100005];edge e[200005];
	void add(int u,int v,int w){
		e[++tot]=(edge){v,w,head[u]},head[u]=tot;
	}
	int cur,dfn[100005],rnk[100005],d[100005],f[22][100005],siz[100005];
	int getmin(int x,int y){
		return ((dfn[x]<dfn[y])?x:y);
	}
	void dfs(int u,int fa){
		dfn[u]=++cur,rnk[cur]=u,f[0][cur]=fa;siz[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;if(v==fa)continue;
			d[v]=d[u]+w;dfs(v,u);siz[u]+=siz[v];
		}
	}
	int getlca(int u,int v){
		if(u==v)return u;
		if((u=dfn[u])>(v=dfn[v]))swap(u,v);
		int o=__lg(v-u++);
		return getmin(f[o][u],f[o][v-(1ll<<o)+1]);
	}
	void init(){
		dfs(1,0);
		for(int j=1;(1ll<<j)<=cur;j++){
			for(int i=1;i+(1ll<<j)-1<=cur;i++){
				f[j][i]=getmin(f[j-1][i],f[j-1][i+(1ll<<(j-1))]);
			}
		}
	}
	int dist(int u,int v){
		return d[u]+d[v]-d[getlca(u,v)]*2;
	}
}t1,t2;
struct Chain{
	int u,v,du,dv,d;
	Chain(const int &_u=0,const int &_v=0,const int &_du=0,const int &_dv=0,const int &_d=0):u(_u),v(_v),du(_du),dv(_dv),d(_du+_dv+_d){}
	bool operator <(const Chain &b)const{
		return d<b.d;
	}
	Chain operator +(const Chain &b)const{
		Chain c=max(*this,b);
		if(u&&b.u)c=max(c,Chain(u,b.u,du,b.du,t1.dist(u,b.u)));
		if(u&&b.v)c=max(c,Chain(u,b.v,du,b.dv,t1.dist(u,b.v)));
		if(v&&b.u)c=max(c,Chain(v,b.u,dv,b.du,t1.dist(v,b.u)));
		if(v&&b.v)c=max(c,Chain(v,b.v,dv,b.dv,t1.dist(v,b.v)));		
		return c;
	}
};
struct segtree{
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define lson l,mid,ls
	#define rson mid+1,r,rs
	Chain c[400005];int tag[400005];
	void pushup(int p){
		c[p]=c[ls]+c[rs];
	}
	void pushdown(int p){
		tag[ls]+=tag[p],tag[rs]+=tag[p];
		if(c[ls].u)c[ls].du+=tag[p];
		if(c[ls].v)c[ls].dv+=tag[p];
		if(c[ls].u&&c[ls].v)c[ls].d+=2*tag[p];
		if(c[rs].u)c[rs].du+=tag[p];
		if(c[rs].v)c[rs].dv+=tag[p];
		if(c[rs].u&&c[rs].v)c[rs].d+=2*tag[p];	
		tag[p]=0;
	}
	void build(int l,int r,int p){
		tag[p]=0;
		if(l==r){
			c[p]=Chain(t1.rnk[l],0,t1.d[t1.rnk[l]],0,0);
			return;
		}
		int mid=(l+r)>>1;
		build(lson);build(rson);
		pushup(p);
	}
	void add(int l,int r,int p,int L,int R,int v){
		if(L>R)return;
		if(L<=l&&r<=R){
			tag[p]+=v;
			if(c[p].u)c[p].du+=v;
			if(c[p].v)c[p].dv+=v;
			if(c[p].u&&c[p].v)c[p].d+=2*v;
			return;
		}
		int mid=(l+r)>>1;pushdown(p);
		if(L<=mid)add(lson,L,R,v);
		if(R>mid)add(rson,L,R,v);
		pushup(p);
	}
	Chain ask(int l,int r,int p,int L,int R){
		if(L<=l&&r<=R)return c[p];
		int mid=(l+r)>>1;pushdown(p);
		if(R<=mid)return ask(lson,L,R);
		if(L>mid)return ask(rson,L,R);
		return ask(lson,L,R)+ask(rson,L,R);
	}
	#undef lson
	#undef rson
	#undef ld
	#undef rs
}Tr;
int T,n,q,qu[500005],qv[500005],ans[500005];vector<int>t[100005];
void solve(int u,int fa){
	Chain l=Tr.ask(1,n,1,1,n);
	for(auto x:t[u]){
		if(l.u)ans[x]=max(ans[x],t1.dist(qu[x],l.u)+t2.dist(l.u,qv[x]));
		if(l.v)ans[x]=max(ans[x],t1.dist(qu[x],l.v)+t2.dist(l.v,qv[x]));		
	}
	for(int i=t2.head[u];i;i=t2.e[i].nxt){
		int v=t2.e[i].v,w=t2.e[i].w;if(v==fa)continue;
		Tr.add(1,n,1,t2.dfn[v],t2.dfn[v]+t2.siz[v]-1,-w);
		Tr.add(1,n,1,1,t2.dfn[v]-1,w);
		Tr.add(1,n,1,t2.dfn[v]+t2.siz[v],n,w);
		solve(v,u);
		Tr.add(1,n,1,t2.dfn[v],t2.dfn[v]+t2.siz[v]-1,w);
		Tr.add(1,n,1,1,t2.dfn[v]-1,-w);
		Tr.add(1,n,1,t2.dfn[v]+t2.siz[v],n,-w);
	}
}
signed main(){
	T=read(),n=read(),q=read();
	for(int i=1,u,v,w;i<n;i++)u=read(),v=read(),w=read(),t1.add(u,v,w),t1.add(v,u,w);
	for(int i=1,u,v,w;i<n;i++)u=read(),v=read(),w=read(),t2.add(u,v,w),t2.add(v,u,w);
	t1.init();t2.init();Tr.build(1,n,1);
	for(int i=1;i<=q;i++)qu[i]=read(),qv[i]=read(),t[qv[i]].push_back(i);
	solve(1,0);for(int i=1;i<=q;i++)printf("%lld\n",ans[i]); 
	return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:


result: