20191101 csp-s模拟T3（dfs序+二维偏序）

T3 层层回忆

3.1 题目背景 他想停下，但是马群奇怪地沉默着。 他不敢打破这奇怪的寂静。 他跑得麻木了。他甚至觉得，自己可以把眼睛闭上。 就在这时，他仿佛真的从前方看到了光，那永恒的，无限追求的光。 他便也沉寂了下来，心安理得地，像其他马那样。 又一次的日出，便笼罩在了这寂静的草原上。

3.2 题目描述 这匹马（我们姑且称其为$Kirito$）想起了若干年以前的一次探险。 那是一个偏远而又神秘的国家。 因为国家是在深山里的，开凿联通城市的道路非常不容易，所以，他们建了最少条数的道路，把所有城市都连了起来。也就是说，这个国家城市之间道路的联系形成了一棵树，每条路的长度都是$1$。 在前往那个国家之前，$Kirito$购买了一份这个国家的地图。他发现，每个城市都有一个因为他本身的历史文化而具有的基础魅力值$a_i$，但是一个城市真正的魅力还取决于它的繁华程度。具体地，一个节点$u$会给他到首都的最短路径上的所有城市再贡献$a_u$点魅力值（不会再给自己贡献，但是会给首都贡献）。 因此，一个城市的魅力值$f_i$就是它的基础魅力值再加上其他城市给他贡献魅力值之和。 现在，$Kirito$想规划一条旅行线路。因为他不是什么毒瘤，所以这条线路一定是从起点到终点的简单路径。 因为不想让自己一开始就受不了或者心理落差太大，作为起点的城市的⁦不能是这条路径经过的所有城市的⁦的最大值或者最小值。 比如，一条由$2$至$4$的路径，经过城市$2,3,1,4$，其中$f_2=2,f_3=3,f_1=4,f_4=2$，这条路径就不行。 现在，每座城市有一个估价函数$g_i$，表示从第$i$座城市出发，能按照上面的规则到达的所有城市的$f$值依次按位或（即⁲或者j）得到的值。 $Kirito$认为这个函数能很好地反应这个城市到底好不好（不接受反驳）。如果一个城市都不能到达，g就是$0$。比如，$1$号城市能到达$2,3,4$号城市。其中$f_2=2,f_3=3,f_1=4,f_4=2$，那么$g_i=2|3|5=7$。 现在，$Kirito$会把城市之间的关系、首都是几号城市，以及每座城市的$a_i$给你，请你帮他计算每座城市的$g$是多少。（救救孩子）

3.3 输入格式 第一行两个正整数$n,capi$，表示城市数和首都编号。 接下来$n-1$行，每行两个数$u,v$，表示有一条连接$u,v$的树边。 接下来一行n个正整数$a_i$，表示每个城市的基础魅力值

3.4 输出格式 一行$n$个整数，第$i$个表示$g_i$。

3.5 输入样例 7 1 1 2 2 3 1 4 4 6 4 7 7 5 2 1 2 1 1 2 1

3.6 输出样例 0 3 1 3 0 1 0

3.7 样例解释 我们可以算出来，$f_1=10,f_2=3,f_3=2,f_4=5,f_6=2,f_7=2$

3.8 数据范围及约定 对于所有数据，保证$\sum a_i\le 10^6,n\le 4\times 10^5$.

思路：

简化题意： 关于$f_i$：本质就是求以i为根的子树的$\sum a_i$。 关于路径：本质就是可以从$i$出发，到达任何不在以$i$为根的子树里的，权值比$i$小的节点。

考虑计算$f_i$。树形dp即可，直接按照含义转移$f_i=a_i+{\sum }_{j是i的子节点}{a}_j$

考虑处理路径。发现$f_i\le f_j(i为j的祖宗节点)$。记录每一个点的$dfs$序（出$[l]$与入$[r]$），对于任意两节点$i,j$，当$l_i<l_j$时，$i$不为$j$的子节点；当$r_i>r_j$时，$i$不为$j$的子节点；且满足以上两条件的点的并集包含所有不在$j$的子树上的点。所以离线后分别以$l$,$r$排序，分别处理二维偏序（以$f_i$做下标，以$f_i$做值）即可。 注意：特判链的情况（要爆递归栈） 或者手动开栈

代码：

#include<bits/stdc++.h> using namespace std; #define in Read() inline char ch(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline int in{ int s=0,f=1;char x; for(x=ch();!isdigit(x);x=ch()) if(x=='-') f=-1; for( ;isdigit(x);x=ch()) s=(s<<1)+(s<<3)+(x&15); return s*f; } const int A=3e6+5; int n,root; int u,v; int maxx=0; int rd[A]; int head[A],tot; struct Road{ int nex,to; }road[A]; inline void ljb(int x,int y){ road[++tot]={head[x],y};head[x]=tot; } int z[A],val[A]; struct dfn{ int l,r,w; }p[A]; int num1,num2; int ans[A]; inline bool comp1(const dfn &x,const dfn &y){ return x.l<y.l; } inline bool comp2(const dfn &x,const dfn &y){ return x.r>y.r; } int tree[2*A]; inline int lowbit(int x){ return x&(-x); } inline void add(int w,int v){ while(w<=maxx){ tree[w]|=v; w+=lowbit(w); } return; } inline int qurey(int w){ int res=0; while(w>0){ res|=tree[w]; w-=lowbit(w); } return res; } inline void DFS(int fa,int x){ val[x]=z[x],p[x].l=++num1; for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(z==fa) continue; DFS(x,z); val[x]+=val[z]; } p[x].r=++num2,p[x].w=x; return; } inline bool find_L(){ int dd=0; for(int i=1;i<=n;i++){ if(rd[i]!=1&&rd[i]!=2) return false; if(rd[i]==1) dd++; if(dd>2) return false; } return true; } signed main(){ n=in,root=in; for(int i=1;i<n;i++){ u=in,v=in; ljb(u,v),ljb(v,u); rd[u]++,rd[v]++; } if(find_L()){ for(int i=1;i<=n;i++) putchar('0'),putchar(' '); return 0; } for(int i=1;i<=n;i++) z[i]=in; DFS(0,root); for(int i=1;i<=n;i++) maxx|=val[i]; sort(p+1,p+1+n,comp1); for(int i=1;i<=n;i++){ if(!val[p[i].w]) continue; ans[p[i].w]|=qurey(val[p[i].w]-1); add(val[p[i].w],val[p[i].w]); } sort(p+1,p+1+n,comp2); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++){ if(!val[p[i].w]) continue; ans[p[i].w]|=qurey(val[p[i].w]-1); add(val[p[i].w],val[p[i].w]); } for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }

手动开栈代码：

#include<bits/stdc++.h> using namespace std; #define in Read() inline char ch(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline int in{ int s=0,f=1;char x; for(x=ch();!isdigit(x);x=ch()) if(x=='-') f=-1; for( ;isdigit(x);x=ch()) s=(s<<1)+(s<<3)+(x&15); return s*f; } const int A=3e6+5; int n,root; int u,v; int maxx=0; int rd[A]; int head[A],tot; struct Road{ int nex,to; }road[A]; inline void ljb(int x,int y){ road[++tot]={head[x],y};head[x]=tot; } int z[A],val[A]; struct dfn{ int l,r,w; }p[A]; int num1,num2; int ans[A]; inline bool comp1(const dfn &x,const dfn &y){ return x.l<y.l; } inline bool comp2(const dfn &x,const dfn &y){ return x.r>y.r; } int tree[2*A]; inline int lowbit(int x){ return x&(-x); } inline void add(int w,int v){ while(w<=maxx){ tree[w]|=v; w+=lowbit(w); } return; } inline int qurey(int w){ int res=0; while(w>0){ res|=tree[w]; w-=lowbit(w); } return res; } inline void DFS(int fa,int x){ val[x]=z[x],p[x].l=++num1; for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(z==fa) continue; DFS(x,z); val[x]+=val[z]; } p[x].r=++num2,p[x].w=x; return; } signed main(){ int size=40<<20;//40M __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size)); n=in,root=in; for(int i=1;i<n;i++){ u=in,v=in; ljb(u,v),ljb(v,u); rd[u]++,rd[v]++; } for(int i=1;i<=n;i++) z[i]=in; DFS(0,root); for(int i=1;i<=n;i++) maxx|=val[i]; sort(p+1,p+1+n,comp1); for(int i=1;i<=n;i++){ if(!val[p[i].w]) continue; ans[p[i].w]|=qurey(val[p[i].w]-1); add(val[p[i].w],val[p[i].w]); } sort(p+1,p+1+n,comp2); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++){ if(!val[p[i].w]) continue; ans[p[i].w]|=qurey(val[p[i].w]-1); add(val[p[i].w],val[p[i].w]); } for(int i=1;i<=n;i++) printf("%d ",ans[i]); exit(0); }