QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693648#5439. Meet in the Middledyj133446WA 0ms22028kbC++143.2kb2024-10-31 16:31:072024-10-31 16:31:25

Judging History

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

  • [2024-10-31 16:31:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:22028kb
  • [2024-10-31 16:31:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;
int T,n,q,st[2][17][N],dfn[2][N],sz[2][N],w[2][N],tot;
ll dis[2][N],ans[5*N],tag[4*N],Tag;
vector<pair<int,int>>e[2][N],Q[N];
struct node{
	int x[2];
	ll val[2];
}tree[4*N];
int Get(int op,int x,int y)
{
	if(dfn[op][x]<dfn[op][y])return x;
	return y;
}
void dfs(int op,int x,int prt)
{
	dfn[op][x]=++tot;w[op][tot]=x,st[op][0][tot]=prt,sz[op][x]=1;
	for(auto y:e[op][x])if(y.first!=prt)
	{
		dis[op][y.first]=dis[op][x]+y.second,dfs(op,y.first,x),sz[op][x]+=sz[op][y.first];
	}
}
int lca(int op,int x,int y)
{
	if(x==y)return x;
	x=dfn[op][x],y=dfn[op][y];
	if(x>y)swap(x,y);
	int k=__lg(y-x);
	return Get(op,st[op][k][x+1],st[op][k][y-(1<<k)+1]);
}
ll getdis(int op,int x,int y)
{
	return dis[op][x]+dis[op][y]-2*dis[op][lca(op,x,y)];
}
void pushdown(int x)
{
	if(tag[x])
	{
		tag[x<<1]+=tag[x],tag[x<<1|1]+=tag[x];
		tree[x<<1].val[0]+=tag[x],tree[x<<1].val[1]+=tag[x];
		tree[x<<1|1].val[0]+=tag[x],tree[x<<1|1].val[1]+=tag[x];
		tag[x]=0;
	}
}
void pushup(int x)
{
	ll maxx=-1e18;
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			ll xx=tree[x<<1].val[i]+tree[x<<1|1].val[j]+getdis(1,tree[x<<1].x[i],tree[x<<1|1].x[j]);
			if(xx>maxx)
			{
				maxx=xx,tree[x].x[0]=tree[x<<1].x[i],tree[x].x[1]=tree[x<<1|1].x[j];
				tree[x].val[0]=tree[x<<1].val[i],tree[x].val[1]=tree[x<<1|1].val[j];
			}
		}
	}
	for(int o=0;o<2;o++)
	{
		ll xx=tree[x<<1|o].val[0]+tree[x<<1|o].val[1]+getdis(1,tree[x<<1|o].x[0],tree[x<<1|o].x[1]);
		if(xx>maxx)maxx=xx,tree[x]=tree[x<<1|o];
	}
}
void build(int x,int l,int r)
{
	tag[x]=0;
	if(l==r)return tree[x].x[0]=tree[x].x[1]=w[0][l],tree[x].val[0]=tree[x].val[1]=getdis(0,1,w[0][l]),void();
	int mid=(l+r)/2;
	build(x<<1,l,mid),build(x<<1|1,mid+1,r);
	pushup(x);
}
void change(int x,int L,int R,int l,int r,ll t)
{
	if(l>r)return;
	if(L>=l&&R<=r)return tag[x]+=t,tree[x].val[0]+=t,tree[x].val[1]+=t,void();
	pushdown(x);
	int mid=(L+R)/2;
	if(l<=mid)change(x<<1,L,mid,l,r,t);
	if(r>mid)change(x<<1|1,mid+1,R,l,r,t);
	pushup(x);
}
void DFS(int x,int prt)
{
	for(auto y:Q[x])ans[y.second]=max(getdis(1,y.first,tree[1].x[0])+tree[1].val[0]+Tag,getdis(1,y.first,tree[1].x[1])+tree[1].val[1]+Tag);
	for(auto y:e[0][x])if(y.first!=prt)
	{
		Tag+=y.second;
		change(1,1,n,dfn[0][y.first],dfn[0][y.first]+sz[0][y.first]-1,-2ll*y.second);
		DFS(y.first,x);
		Tag-=y.second;
		change(1,1,n,dfn[0][y.first],dfn[0][y.first]+sz[0][y.first]-1,2ll*y.second);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	T=1;
	while(T--)
	{
		cin>>n,Tag=0;
		for(int i=1;i<=n;i++)e[0][i].clear(),e[1][i].clear(),Q[i].clear();
		for(int i=0;i<2;i++)
		{
			for(int j=1;j<n;j++)
			{
				int x,y,z;
				cin>>x>>y>>z;
				e[i][x].emplace_back(y,z),e[i][y].emplace_back(x,z);
			}
			tot=0,dfs(i,1,0);
		}
		for(int i=0;i<2;i++)
		{
			for(int j=1;j<17;j++)
			{
				for(int k=1;k+(1<<j)-1<=n;k++)st[i][j][k]=Get(i,st[i][j-1][k],st[i][j-1][k+(1<<(j-1))]);
			}
		}
		cin>>q;
		for(int i=1;i<=q;i++)
		{
			int x,y;
			cin>>x>>y,ans[i]=0,Q[x].emplace_back(y,i);
		}
		build(1,1,n),DFS(1,0);
		for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 22028kb

input:

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

output:

12

result:

wrong answer 1st numbers differ - expected: '6', found: '12'