[SDOI2020]Day2T2 tree 解题报告

· · 题解

题目大意

给定一棵以1为根的有根树，记 d(u,v) 为 u\to v 简单路径上的边数， w(u) 为点 u 的权值，val(u)=\sum_{v}d(u,v)+w(v)。其中， v 是 u 的子树内的点（包括点 u ）。求 \sum_{i=1}^{n}val(i)。

解题报告

模拟这个过程，在 dfs 中，我们发现每次都要将子树内的点的 w 值整体+1，再求子树内的异或和。所以，我们需要一种工具，支持子树加一、插入一个数和查询子树异或和这三种操作。

解决位运算问题，第一要想到的是01tire。便于实现，我们先把每个点从低位到高位建一棵01tire。那么每次的操作就是：dfs 孩子，将孩子的01tire合并，再把合并后的 01tire 整体 +1，最后插入 w(x)，整体求值。

01tire 的合并和线段树合并一样，把每个点的权值对应相加即可，复杂度 O(log \; W)。

01tire 的整体 +1，就是把点 x 的左儿子和右儿子同时 +1，那么左儿子(0)加一就变成了右儿子。这里，我们每个点记一个结束标记 ed。如果点 x 有结束标记，那么左儿子加一后变成的右儿子，也应该补上一个结束标记。注意：如果点 x 原先没有左儿子，应该新建一个点进行操作。而右儿子整体+1就变成了左儿子，再递归处理即可，复杂度 O(log \;W)。（code below）

void add1(int x){
    if(!x)return;
    swap(tr[x].c[0],tr[x].c[1]);
    if(tr[x].ed && !tr[x].c[1])tr[x].c[1]=++cur;
    tr[tr[x].c[1]].ed^=tr[x].ed;
        tr[tr[x].c[1]].cnt^=tr[x].ed; tr[x].ed=0;
    add1(tr[x].c[0]); updata(x);
}

01tire的插入即为普通的插入，复杂度O(log \;W)

最后是updata，一个点的权值，是左儿子的权值乘2异或右儿子的权值乘2，因为右儿子代表最低位为1，如果右儿子子树内有奇数的串，那么还要把这个点的权值加一，所以还要记一个 cnt 代表子树内串的个数的奇偶性。(code below)

void updata(int x){
    int ls=tr[x].c[0],rs=tr[x].c[1];
    tr[x].cnt=tr[x].ed^tr[ls].cnt^tr[rs].cnt;
    tr[x].val=((tr[ls].val<<1)^((tr[rs].val<<1)|tr[rs].cnt));
}

考场上，我做这道题的心路历程是艰难而漫长的，我会写在代码的下面，有兴趣的oier可以了解一下qwq。

考场代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=552020;
long long ans;
int n,tot,cur,v[N],w[N],rt[N];
struct trie{int cnt,val,ed,c[2];}tr[N*27];
struct Edge{int to,next;}e[N];
void add(int x,int y){
    e[++tot].to=y; e[tot].next=v[x]; v[x]=tot;
}
void updata(int x){
    int ls=tr[x].c[0],rs=tr[x].c[1];
    tr[x].cnt=tr[x].ed^tr[ls].cnt^tr[rs].cnt;
    tr[x].val=((tr[ls].val<<1)^((tr[rs].val<<1)|tr[rs].cnt));
}
void ins(int &x,int y){
    if(!x)x=++cur;
    if(!y){tr[x].ed^=1;tr[x].cnt^=1;return;}
    ins(tr[x].c[y&1],y>>1); updata(x);
}
void add1(int x){
    if(!x)return;
    swap(tr[x].c[0],tr[x].c[1]);
    if(tr[x].ed && !tr[x].c[1])tr[x].c[1]=++cur;
    tr[tr[x].c[1]].ed^=tr[x].ed; tr[tr[x].c[1]].cnt^=tr[x].ed; tr[x].ed=0;
    add1(tr[x].c[0]); updata(x);
}
int merge(int x,int y){
    if(!x || !y)return x|y;
    tr[x].ed^=tr[y].ed;
    tr[x].cnt^=tr[y].cnt;
    tr[x].val^=tr[y].val;
    tr[x].c[0]=merge(tr[x].c[0],tr[y].c[0]);
    tr[x].c[1]=merge(tr[x].c[1],tr[y].c[1]);
    return x;
}
void dfs(int x){
    ins(rt[x],w[x]);
    for(int p=v[x];p;p=e[p].next){
        int kp=e[p].to; dfs(kp);
        add1(rt[kp]);// cout<<"+"<<kp<<":"<<tr[rt[kp]].val<<endl;
        rt[x]=merge(rt[x],rt[kp]);
    } ans+=1ll*tr[rt[x]].val;
//  cout<<x<<"val="<<tr[rt[x]].val<<endl;
}
int read(){
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)w[i]=read();
    for(int i=2;i<=n;i++)add(read(),i);
    dfs(1); printf("%lld",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}
/*
5
1 1 1 4 1 
1 1 3 4 

3
1 4 1
1 2

*/

心路历程

Day2，看完题觉得T1的30pts，T2的10pts，T3的50pts比较容易。最后觉得树的问题比较有趣，就开了T2。终于，在9:20的时候想到做法，10:00就过了大样例，但是，一拍起来，不管大数据小数据都出错（CCF垃圾大样例）。于是，我就进入了艰难的调试，从10:00到11:00，再到12:00......在十二点，我知道时间所剩不多了，心想：写写 T3 暴力都交暴力，T2 弃了算了。但我想起了我的诺言：“我lindongli2004永不放弃，我lindongli2004永不认输 。 ”于是，我在草稿纸上疯狂地画着，调着。草稿纸画满了，再用准考证的背面，汗水汇成条条小溪留下。最后，我加了个结束标记，终于在考试结束前15min，ffcc.bat 跑得飞快——我过了！一看时间，T3暴力没法打了，就敲了个m=n-1的情况，没想到还有5pts。如果省选像往常5个小时，我想T3的50pts还是应该能拿到的吧。

现在回想当成在考场上的抉择，真的不寒而栗——如果T2没调出来会是什么结果？我当时真的没想过。可能这就是青春吧，爱拼才会赢。（虽然还是无法摆脱我菜的事实）

额，最后插一句，能不能有大神教教我，前两段“永不认输”后面的那个句号是放在引号内还是引号外？qwq