[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） ```cpp 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。 考场代码： ```cpp #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