/ Randle /

记录详情

Accepted

/in/foo.cc: In function 'int main()':
/in/foo.cc:87:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(x!=y)all+=2;int mi=x1,all1=all;all=(all+1)/2;
   ^~
/in/foo.cc:87:18: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the 'if'
   if(x!=y)all+=2;int mi=x1,all1=all;all=(all+1)/2;
                  ^~~
/in/foo.cc:82:17: warning: unused variable 'ans' [-Wunused-variable]
   int x1=x,y1=y,ans,xx,yy,all=0;
                 ^~~
/in/foo.cc:82:21: warning: unused variable 'xx' [-Wunused-variable]
   int x1=x,y1=y,ans,xx,yy,all=0;
                     ^~
/in/foo.cc:82:24: warning: unused variable 'yy' [-Wunused-variable]
   int x1=x,y1=y,ans,xx,yy,all=0;
                        ^~
# 状态 耗时 内存占用
#1 Accepted 8ms 444.0 KiB
#2 Accepted 3ms 336.0 KiB
#3 Accepted 1ms 332.0 KiB
#4 Accepted 82ms 16.703 MiB
#5 Accepted 82ms 16.664 MiB
#6 Accepted 85ms 16.641 MiB
#7 Accepted 198ms 16.625 MiB
#8 Accepted 193ms 16.695 MiB
#9 Accepted 197ms 16.707 MiB
#10 Accepted 178ms 16.625 MiB

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+8;
int n,i,j,k,m,tot,hd[N],x,y,z,allz,g[N][21],f[N],d[N],l[N],r[N],s[2][2*N],now,wh[2*N],bf[N];
struct arr{
	int d,nc,l;
}p[200008];
struct arr1{
	int d,w;
}q[200008];
void ins(int x,int y,int l){p[++tot]=(arr){y,hd[x],l};hd[x]=tot;}
bool cmp(arr1 a,arr1 b)
{
	return a.d>b.d;
}
void search(int x,int fa,int dep)
{
	g[x][0]=p[fa].d;d[x]=dep;l[x]=r[x]=now+1;bf[x]=fa;
	for(i=1;(1<<i)<dep;i++)
	  g[x][i]=g[g[x][i-1]][i-1];
	if(x!=1)now++;
	for(int z=hd[x];z;z=p[z].nc)
	  if(z!=fa)now++;
	for(int z=hd[x];z;z=p[z].nc)
	  if(z!=fa)
	  {
	    search(p[z].d,z^1,dep+1);
	    f[x]+=f[p[z].d]+p[z].l;
	    q[r[x]].d=f[p[z].d]+p[z].l;q[r[x]++].w=z^1;
	  }
	if(x!=1)q[r[x]].d=allz-f[x],q[r[x]].w=fa^1;
	else r[x]--;
	sort(q+l[x],q+1+r[x],cmp);
}
int work(int l,int r,int p)
{
	if(l%2!=p)l++;
	if(r%2!=p)r--;
	return s[p][r]-s[p][l-2];
}
int solve(int l,int r,int xs,int hs)
{
	if(xs==0)return work(l,wh[hs]-1,l%2)+work(wh[hs]+1,r,1-l%2);
	if(hs==0)return work(l,wh[xs]-1,l%2)+work(wh[xs]+1,r,1-l%2)+q[wh[xs]].d; 
	if(wh[xs]<wh[hs])return work(l,wh[xs]-1,l%2)+work(wh[xs]+1,wh[hs]-1,1-l%2)+work(wh[hs]+1,r,l%2)+q[wh[xs]].d;
	else return work(l,wh[hs]-1,l%2)+work(wh[hs]+1,wh[xs]-1,1-l%2)+work(wh[xs]+1,r,l%2)+q[wh[xs]].d;
}
int main()
{
	//freopen("b.in","r",stdin);
	//freopen("b1.out","w",stdout);
	scanf("%d %d",&n,&m);
	tot=1;
	for(i=1;i<n;i++)
	{
		scanf("%d %d %d",&x,&y,&z);ins(x,y,z);ins(y,x,z);
		allz+=z;
	}
	search(1,0,1);
	for(i=1;i<=now;i++)
	{
	  s[i%2][i]=s[i%2][i-2]+q[i].d;
	  wh[q[i].w]=i;
	}
	while(m--)
	{
		scanf("%d %d",&x,&y);bool t=false;
		if(x==y)
		{
			printf("%d\n",work(l[x],r[x],l[x]%2));
			continue;
		}
		if(d[x]<d[y])x^=y^=x^=y,t=true;
		if(g[x][0]==y)
		{
			if(!t)printf("%d\n",allz-solve(l[y],r[y],0,bf[x]));
			else printf("%d\n",allz-solve(l[x],r[x],0,bf[x]^1));
			continue;
		}
		int x1=x,y1=y,ans,xx,yy,all=0;
		for(i=20;i>=0;i--)
		  if(d[x]-d[y]>=(1<<i))x=g[x][i],all+=(1<<i);
		for(i=20;i>=0;i--)
		  if(g[x][i]!=g[y][i])x=g[x][i],y=g[y][i],all+=(1<<(i+1));
		if(x!=y)all+=2;int mi=x1,all1=all;all=(all+1)/2;
		for(i=20;i>=0;i--)
		  if((1<<i)<=all)mi=g[mi][i],all-=(1<<i);
		if(d[x1]==d[y1])printf("%d\n",solve(l[mi],r[mi],bf[x],bf[y]));
		else 
		{
			int mi2=x1,mi1=x1;all=all1/2;
			for(i=20;i>=0;i--)
		      if((1<<i)<=all)mi2=g[mi2][i],all-=(1<<i);
			all=all1/2-1;
			for(i=20;i>=0;i--)
		      if((1<<i)<=all)mi1=g[mi1][i],all-=(1<<i);
			if(all1%2==0)
			{
			  if(t)printf("%d\n",solve(l[mi],r[mi],bf[mi]^1,bf[mi1]));
			  else printf("%d\n",solve(l[mi],r[mi],bf[mi1],bf[mi]^1));
			}
			else
			{
			  if(t)printf("%d\n",allz-solve(l[mi2],r[mi2],bf[mi1],bf[mi2]^1));
			  else
			  {
			  	int p=all1/2-1,bff;y=y1;
			  	for(i=20;i>=0;i--)
			  	  if((1<<i)<=p)y=g[y][i],p-=(1<<i);
			  	if(d[y1]+1==d[x1])bff=bf[y];else bff=bf[mi]^1;
			    printf("%d\n",allz-solve(l[mi],r[mi],bff,bf[mi2]));
			  }
			}
		}
	}
	return 0;
}

信息

递交者
类型
递交
题目
树上角斗 T2
题目数据
下载
语言
C++
递交时间
2019-02-24 14:37:02
评测时间
2019-02-24 14:37:02
评测机
分数
100
总耗时
1032ms
峰值内存
16.707 MiB