这道题也是很简单的树剖啊……（虽然说大佬们都用了什么树上差分……但是这题暴力树剖真能过）
其实N = 300000有点卡nlog^2n,不过这题数据好像比较水还是能过的。
直接用树剖维护，每次走过一条路径就把上面所有的点值全部++，最后输出每个点被走过多少次即可。
不过这里就有了BUG！我们上面这么计算是会导致除了起始点之外每个点被多算了一次，在输出结果的时候要-1.（然后我脑子非常智障，最后答案传参都不对）
然后就有了40分钟写不完树剖板子题的笑话…………
唉，我到底是练树剖还是练线段树啊……
看一下代码吧。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 300005; const int INF = 100000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to; }e[M<<1]; struct seg { int v,lazy; }t[M<<2]; int n,m,x,y,dfn[M],size[M],head[M],hson[M],top[M],fa[M],rk[M],a[M],ecnt,dep[M],idx,pos[M]; bool flag = 0; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void dfs1(int x,int f,int depth) { size[x] = 1,fa[x] = f,dep[x] = depth; int maxson = -1; for(int i = head[x];i;i = e[i].next) { if(e[i].to == f) continue; dfs1(e[i].to,x,depth+1); size[x] += size[e[i].to]; if(size[e[i].to] > maxson) maxson = size[e[i].to],hson[x] = e[i].to; } } void dfs2(int x,int t) { top[x] = t,dfn[x] = ++idx; if(!hson[x]) return; dfs2(hson[x],t); for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa[x] || e[i].to == hson[x]) continue; dfs2(e[i].to,e[i].to); } } void pushdown(int p,int l,int r) { int mid = (l+r) >> 1; t[p<<1].lazy += t[p].lazy,t[p<<1|1].lazy += t[p].lazy; t[p<<1].v += (mid - l + 1) * t[p].lazy,t[p<<1|1].v += (r - mid) * t[p].lazy; t[p].lazy = 0; } void modify(int p,int l,int r,int kl,int kr) { if(l == kl && r == kr) { //printf("@%d %d ",l,r); t[p].lazy++,t[p].v += (r-l+1); return; } int mid = (l+r) >> 1; if(t[p].lazy) pushdown(p,l,r); if(kr <= mid) modify(p<<1,l,mid,kl,kr); else if(kl > mid) modify(p<<1|1,mid+1,r,kl,kr); else modify(p<<1,l,mid,kl,mid),modify(p<<1|1,mid+1,r,mid+1,kr); t[p].v = t[p<<1].v + t[p<<1|1].v; } int query(int p,int l,int r,int pos) { if(l == r) return t[p].v; int mid = (l+r) >> 1; if(t[p].lazy) pushdown(p,l,r); if(pos <= mid) return query(p<<1,l,mid,pos); else return query(p<<1|1,mid+1,r,pos); } void mrange(int x,int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); modify(1,1,n,dfn[top[x]],dfn[x]); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); //printf("!%d %d ",dfn[x],dfn[y]); modify(1,1,n,dfn[x],dfn[y]); } int main() { n = read(); rep(i,1,n) a[i] = read(); rep(i,1,n-1) x = read(),y = read(),add(x,y),add(y,x); dfs1(1,0,1),dfs2(1,1); rep(i,1,n-1) { mrange(a[i],a[i+1]); //rep(j,1,n) printf("#%d ",query(1,1,n,j));enter; } rep(i,1,n) { if(i == a[1]) rk[i] = query(1,1,n,dfn[i]); else rk[i] = query(1,1,n,dfn[i])-1; } rep(i,1,n) printf("%d ",rk[i]); return 0; }