1 条题解

  • 2
    @ 2021-8-27 17:32:39

    题目传送门

    欢迎踩博客

    题目大意

    给定一颗以 11 为根的带权树,对于每个询问 {x,h}\{x,h\},求子树 xxhh 层节点权值的异或和。

    算法分析:

    其实这道题算法还是蛮多的~~(毕竟是签到题,当然要水水水水)~~。

    这里介绍一种用树状数组的离线算法。

    一些约定:

    • disidis_i 表示城市 ii 在树上的深度。

    事实上,在对整棵树进行深搜的同时,可以用一个全局的树状数组来实时维护整棵树前 hh 层的节点权值和。具体的,先预处理与 xx 有关的询问。利用差分思想,在处理 xx 的子树前,记录未处理子树时前 disi+hdis_i+h 层异或和,并将点 xx 插入树状数组。在回溯时,针对关于 xx 的不同 hh,用前 disi+hdis_i+h 层新的异或和异或未处理时的异或和,就可以得到在 xx 的子树中的异或和。储存到对应下标即可。

    时间复杂度为 O(nlogn)\mathcal{O}(n\log n),空间复杂度为 O(n)\mathcal{O}(n)

    code:

    #include<bits/stdc++.h>
    #define ll long long
    #define reg register
    #define rint reg int
    #define F(i,a,b) for(reg int i=(a);i<=(b);++i)
    using namespace std;
    bool beginning;
    inline int read();
    const int N=1e6+5,E=N<<1;
    int n,m,a[N];
    ll val[N];
    int ver[E],net[E],head[N],tot;
    inline void add(int x,int y) {
    	ver[++tot]=y,net[tot]=head[x],head[x]=tot;
    }
    struct P {
    	int x,h,id;
    	bool operator <(const P& a)const {
    		return x<a.x;
    	}
    } q[N];
    int dis[N];
    ll c[N],ans[N];
    inline void insert(int x,ll y) {
    	if(!x)c[0]+=y;
    	else while(x<=n)c[x]^=y,x+=x&-x;
    }
    inline ll query(int x) {
    	if(!x)return c[0];
    	ll sum=0;
    	while(x)sum^=c[x],x-=x&-x;
    	return sum;
    }
    vector<int>f[N];
    void dfs(int x,int fath) {
    	dis[x]=dis[fath]+1;
    	vector<ll>pos;
    	for(reg int i=0; i<f[x].size(); ++i) {//记录未处理时的值 
    		int k=f[x][i];
    		pos.push_back(query(q[k].h+dis[x]));
    	}
    	insert(dis[x],val[x]);//插入x 
    	for(reg int i=head[x]; i; i=net[i]) {
    		int &y=ver[i];
    		if(y==fath)continue;
    		dfs(y,x);
    	}
    	for(reg int i=0; i<f[x].size(); ++i) {//“差分” 
    		int k=f[x][i];
    		ans[k]=query(q[k].h+dis[x])^pos[i];
    	}
    }
    bool ending;
    int main() {
    //  printf("%.2lfMB\n",1.0*(&ending-&beginning)/1024/1024);
    	n=read(),m=read();
    	F(i,1,n)val[i]=read();
    	F(i,2,n) {
    		a[i]=read();
    		add(i,a[i]),add(a[i],i);
    	}
    	F(i,1,m)q[i].x=read(),q[i].h=read(),f[q[i].x].push_back(i);//记录询问 
    	dfs(1,0);
    	F(i,1,m) {
    		printf("%.3f",1.0*ans[i]/1e3+1e-4);
    		if(i!=m)putchar('\n');
    	}
    	return 0;
    }
    inline int read() {
    	reg int x=0;
    	reg char c=getchar();
    	while(!isdigit(c))c=getchar();
    	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    	return x;
    }
    

    除了树状数组,本题还可以使用主席树,树套树等数据结构维护。

    其实还有 O(n)\mathcal{O}(n) 的做法,思路和上面的树状数组基本一致,就不多讲了,下面给出代码。

    #include <bits/stdc++.h>
    #define reg register
    using namespace std;
    const int M=1000005;
    inline void Rd(int &x) {
    	x=0;
    	reg char c=getchar();
    	while(!isdigit(c))c=getchar();
    	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    }
    int n,m;
    int head[M],tot=0;
    struct eg {
    	int v,nxt;
    } E[M];
    struct qq {
    	int k,id;
    };
    vector<qq>ask[M];
    int w[M],sub[M],ans[M],sum[M*2];
    void solve(int u,int d) {
    	for(reg int j=0,sz=ask[u].size(); j<sz; ++j)
    		ans[ask[u][j].id]^=sum[d+ask[u][j].k+1];
    	sub[u]=w[u];
    	for(reg int j=head[u]; j; j=E[j].nxt)
    		solve(E[j].v,d+1),sub[u]^=sub[E[j].v];
    	sum[d]^=sub[u];
    	for(reg int j=0,sz=ask[u].size(); j<sz; ++j)
    		ans[ask[u][j].id]^=sub[u]^sum[d+ask[u][j].k+1];
    }
    int main() {
    	Rd(n),Rd(m);
    	for(reg int i=1; i<=n; ++i)Rd(w[i]);
    	for(reg int i=2,fa; i<=n; ++i) {
    		Rd(fa);
    		E[++tot]=(eg) {
    			i,head[fa]
    		};
    		head[fa]=tot;
    	}
    	for(reg int i=1,u,k; i<=m; ++i) {
    		Rd(u),Rd(k);
    		ask[u].push_back((qq) {
    			k,i
    		});
    	}
    	solve(1,1);
    	for(reg int i=1; i<=m; ++i) {
    		printf("%.3f", ans[i]/1000.0);
    		if(i<m) putchar(10);
    	}
    }
    

    第一次出公开赛,希望大家玩得开心~

    • 1

    信息

    ID
    181
    时间
    1000~2000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    52
    已通过
    7
    上传者