[CSP-S模拟测试]:C（倍增+数学）

题目传送门（内部题152）

输入格式

　　第一行两个整数$N,Q$。
　　接下来一行$N$个整数，第$i$个为$a_i$。
　　接下来的$N-1$行，每行两个整数$u,v$。表示$u,v$之间有一条边。
　　接下来的$Q$行，每行两个整数$u,v$。表示一组询问。

输出格式

　　对于每个询问，输出一行一个整数表示答案。

样例

样例输入：

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

样例输出：

13
7

数据范围与提示

　　每个测试点10$分，共$10$个测试点：

　　对于所有的数据，有：$1\leqslant N,Q,0\leqslant a_i<323232323$

题解

题目没多难，用倍增维护父亲，每一位的前缀和，向上的答案即可。

我的打法跟正解不太一样，被卡空间了$\downarrow$

不过结果还是好的啦～

说来也神奇，晚上做了个梦，突然想到了一种优化方式；早上过来没多久就$A$啦，真的是做梦都在码代码。

时间复杂度：$\Theta(n\log n)$.。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

#define int int_least32_t

using namespace std;

struct rec{int nxt,to;}e[600001];

struct node{int x,y,lca;}q[300001];

int head[600001],cnt;

int N,Q;

int a[600001];

int depth[600001],fa[600001][21];

pair<int,short> c[21];

int_least64_t val[600001][21],up[600001][21],ans[300001];

void dfs(int x)

{

	for(int i=head[x];i;i=e[i].nxt)

	{

		if(depth[e[i].to])continue;

		depth[e[i].to]=depth[x]+1;

		fa[e[i].to][0]=x;

		up[e[i].to][0]=a[e[i].to];

		for(short j=1;j<21;j++)fa[e[i].to][j]=fa[fa[e[i].to][j-1]][j-1];

		for(short j=0;j<21;j++)val[e[i].to][j]=val[x][j]+((a[e[i].to]&(1<<j))>0);

		for(short j=1;j<21;j++)up[e[i].to][j]=up[e[i].to][j-1]+up[fa[e[i].to][j-1]][j-1]+1LL*(1<<(j-1))*((1<<(j-1))-val[fa[e[i].to][j-1]][j-1]+val[fa[e[i].to][j]][j-1]);

		dfs(e[i].to);

	}

}

void dfs(int x,int fat)

{

	for(int i=head[x];i;i=e[i].nxt)

	{

		if(e[i].to==fat)continue;

		up[e[i].to][0]=a[e[i].to];

		for(short j=1;j<21;j++)up[e[i].to][j]=up[e[i].to][j-1]+up[fa[e[i].to][j-1]][j-1]+1LL*(1<<(j-1))*((1<<(j-1))-val[e[i].to][j-1]+val[fa[e[i].to][j-1]][j-1]);

		dfs(e[i].to,x);

	}

}

int get(int x,int dep){for(short i=0;i<21;i++)if(dep&(1<<i))x=fa[x][i];return x;}

int LCA(int x,int y)

{

	if(depth[x]>depth[y])swap(x,y);

	for(short i=20;i>=0;i--)

		if(depth[fa[y][i]]>=depth[x])y=fa[y][i];

	if(x==y)return x;

	for(short i=20;i>=0;i--)

		if(fa[x][i]!=fa[y][i])

		{x=fa[x][i];y=fa[y][i];}

	return fa[x][0];

}

long long ask1(int x,int y)

{

	if(x==y)return 0;

	long long res=0;

	for(short i=19;i>=0;i--)

		if(depth[fa[x][i]]>=depth[y])

		{

			res+=up[x][i];

			x=fa[x][i];

			res+=(depth[x]-depth[y]-(val[x][i]-val[y][i]))*(1<<i);

		}

	return res;

}

long long ask2(int x,int y)

{

	if(x==y)return a[x];

	if(depth[x]>depth[y])return 0;

	short top=0;

	long long res=0;

	int now=y;

	for(short i=0;i<21;i++)

		if((depth[y]-depth[x]+1)&(1<<i))

		{

			c[++top]=make_pair(now,i);

			now=fa[now][i];

		}

	for(short i=top;i;i--)

	{

		res+=up[c[i].first][c[i].second];

		if(c[i].second)

			res+=1LL*(1<<(c[i].second))*(depth[y]-depth[c[i].first]-(val[y][c[i].second]-val[c[i].first][c[i].second]));

	}

	return res;

}

int main()

{

	scanf("%d%d",&N,&Q);

	for(int i=1;i<=N;i++)scanf("%d",&a[i]);

	for(int i=1;i<N;i++)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		e[++cnt]=(rec){head[x],y};head[x]=cnt;

		e[++cnt]=(rec){head[y],x};head[y]=cnt;

	}

	depth[N<<1]=1;

	for(int x=N<<1;x>N+1;x--)

	{

		depth[x-1]=depth[x]+1;

		fa[x-1][0]=x;

		for(short j=1;j<21;j++)fa[x-1][j]=fa[fa[x-1][j-1]][j-1];

	}

	depth[1]=depth[N+1]+1;

	fa[1][0]=N+1;

	up[1][0]=a[1];

	for(short j=1;j<21;j++)fa[1][j]=fa[fa[1][j-1]][j-1];

	for(short j=0;j<21;j++)val[1][j]=val[N+1][j]+((a[1]&(1<<j))>0);

	for(short j=1;j<21;j++)up[1][j]=up[1][j-1]+up[fa[1][j-1]][j-1]+1LL*(1<<(j-1))*((1<<(j-1))-val[fa[1][j-1]][j-1]+val[fa[1][j]][j-1]);

	dfs(1);

	for(int i=1;i<=Q;i++)

	{

		scanf("%d%d",&q[i].x,&q[i].y);

		q[i].lca=LCA(q[i].x,q[i].y);

		ans[i]=ask1(q[i].x,q[i].lca);

	}

	up[1][0]=a[1];

	for(short j=1;j<21;j++)up[1][j]=up[1][j-1]+up[fa[1][j-1]][j-1]+1LL*(1<<(j-1))*((1<<(j-1))-val[1][j-1]+val[fa[1][j-1]][j-1]);

	dfs(1,0);

	for(int i=1;i<=Q;i++)

	{

		int res=get(q[i].lca,depth[q[i].x]-depth[q[i].lca]);

		printf("%lld\n",ans[i]+ask2(res,q[i].y)-ask2(res,fa[q[i].lca][0]));

	}

	return 0;

}

rp++

巴特西