QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#483056#5439. Meet in the MiddleHadtstiWA 11ms38528kbC++142.9kb2024-07-18 10:23:412024-07-18 10:23:42

Judging History

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

  • [2024-07-18 10:23:42]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:38528kb
  • [2024-07-18 10:23:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,q,x,y,z,ans[500010];
vector<pair<int,int> >Q[100010];
struct TREE
{
	int fa[100010],dfn[100010],rk[100010],num,sz[100010],son[100010],d[100010],top[100010];
	long long dis[100010];
	vector<pair<int,int> >E[100010];
	void dfs1(int x)
	{
		d[x]=d[fa[x]]+1;
		sz[x]=1;
		for(auto [y,z]:E[x])
			if(y!=fa[x])
			{
				fa[y]=x;
				dis[y]=dis[x]+z;
				dfs1(y);
				sz[x]+=sz[y];
				if(sz[y]>sz[son[x]])
					son[x]=y;
			}
	}
	void dfs2(int x,int tp)
	{
		dfn[x]=++num;
		rk[num]=x;
		top[x]=tp;
		if(!son[x])
			return;
		dfs2(son[x],tp);
		for(auto [y,z]:E[x])
			if(y!=son[x]&&y!=fa[x])	
				dfs2(y,y);
	}
	int LCA(int x,int y)
	{
		while(top[x]!=top[y])	
		{
			if(d[top[x]]<d[top[y]])
				swap(x,y);
			x=fa[top[x]];
		}
		return d[x]<d[y]?x:y;
	}
	long long len(int x,int y)
	{
		return x&&y?dis[x]+dis[y]-2*dis[LCA(x,y)]:0;
	}
}T1,T2;
struct path
{
	struct point
	{
		int x;
		long long dis;
	}S,T;
	long long dis; 
	path(point s={0,0},point t={0,0}){S=s,T=t,dis=T2.len(S.x,T.x)+S.dis+T.dis;}
	friend bool operator <(path a,path b)
	{
		return a.dis<b.dis;
	}
	friend path operator +(path a,path b)
	{
		return max(max(max(a,b),max(path(a.S,b.S),path(a.T,b.T))),max(path(a.S,b.T),path(a.T,b.S)));
	}
};
struct node
{
	path P;
	long long tag;
}tr[400010];
void addtag(int p,long long tag)
{
	tr[p].P.S.dis+=tag;
	tr[p].P.T.dis+=tag;
	if(tr[p].P.T.x)
		tr[p].P.dis+=2ll*tag;
	tr[p].tag+=tag;
}
void pushdown(int p)
{
	if(tr[p].tag)
	{
		addtag(p<<1,tr[p].tag);
		addtag(p<<1|1,tr[p].tag);
		tr[p].tag=0;
	}
}
void build(int p=1,int l=1,int r=n)
{
	if(l==r)
	{
		tr[p]={path({T1.rk[l],T1.dis[T1.rk[l]]}),0};
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tr[p].P=tr[p<<1].P+tr[p<<1|1].P;
}
void change(int p,int L,int R,long long v,int l=1,int r=n)
{
	if(l>=L&&r<=R)
		return addtag(p,v);
	pushdown(p);
	int mid=l+r>>1;
	if(mid>=L)
		change(p<<1,L,R,v,l,mid);
	if(mid<R)
		change(p<<1|1,L,R,v,mid+1,r);
	tr[p].P=tr[p<<1].P+tr[p<<1|1].P;
}
void upd(int L,int R,long long v)
{
	change(1,1,n,v);
	change(1,L,R,-2ll*v);
}
long long ask(int x)
{
	return max(T2.len(x,tr[1].P.S.x)+tr[1].P.S.dis,T2.len(x,tr[1].P.T.x)+tr[1].P.T.dis);
}
void calc(int x)
{
	for(auto [y,z]:Q[x])
		ans[z]=ask(y);
	for(auto [y,z]:T1.E[x])
		if(y!=T1.fa[x])
		{
			upd(T1.dfn[y],T1.dfn[y]+T1.sz[y]-1,z);
			calc(y);
			upd(T1.dfn[y],T1.dfn[y]+T1.sz[y]-1,-z);
		}
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		T1.E[x].push_back({y,z});
	}
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		T2.E[x].push_back({y,z});
	}
	T1.dfs1(1);
	T1.dfs2(1,1);
	T2.dfs1(1);
	T2.dfs2(1,1);
	build();
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		Q[x].push_back({y,i});
	}
	calc(1);
	for(int i=1;i<=q;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 33152kb

input:

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

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

score: 0
Accepted
time: 3ms
memory: 38528kb

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 33380kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 11ms
memory: 37340kb

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st numbers differ - expected: '647838384844', found: '0'