鏈接：https://ac.nowcoder.com/acm/problem/14415
來源：牛客網(wǎng)

題目描述
wyf非常喜歡樹。一棵有根數(shù)樹上有N個(gè)節(jié)點(diǎn)，1號(hào)點(diǎn)是他的根，每條邊都有一個(gè)距離，而wyf是個(gè)愛問奇怪問題的熊孩子，他想知道對(duì)于某個(gè)點(diǎn)x,以x為根的子樹上，所有與x距離大于等于k的點(diǎn)與x的距離之和。
輸入描述:
第一行一個(gè)正整數(shù)N

接下來N-1描述這棵樹，每行兩個(gè)數(shù)第i行兩個(gè)數(shù)p和D表示樹上有一條p到i+1長(zhǎng)度為D的邊。(p<=i)

下面一行一個(gè)正整數(shù)Q表示wyf的詢問次數(shù)。

接下來Q行每行兩個(gè)正整數(shù)x和k。 (1<=N,Q<=2x105,1<=D,K<=106)

輸出描述:
對(duì)于每次詢問x,k輸出以x為根的子樹上，所有與x距離大于等于k的點(diǎn)與x的距離之和。(若不存在這樣的點(diǎn)，則輸出應(yīng)為0)
示例1
輸入
復(fù)制
3
1 2
1 3
2
1 3
1 2
輸出
復(fù)制
3
5
題目要求求x的子樹中所有距離x點(diǎn)大于等于k的點(diǎn)與x的距離和。
首先題目給出了一個(gè)根節(jié)點(diǎn)，我們把所有點(diǎn)到根節(jié)點(diǎn)的距離計(jì)算出來。題目讓我們求到x的距離，我們可以轉(zhuǎn)化成到根節(jié)點(diǎn)的距離，那么這個(gè)題目就轉(zhuǎn)化成了求x的子樹中點(diǎn)到根節(jié)點(diǎn)的距離大于dis[x]+k的個(gè)數(shù)dis_num，和他們的總共的距離dis_sum。利用主席樹求出來之后，再用
dis_sum-(dis_num*dis[x])，這就是題目所求。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=2e5+100; struct node{int l;int r;ll sum;ll num; }p[maxx*40]; struct edge{int to,next;ll w; }e[maxx<<1]; int head[maxx<<1],in[maxx],out[maxx]; int root[maxx]; ll dis[maxx]; int n,m,tot,ror,sign; /*-----------事前準(zhǔn)備------------*/ inline void init() {memset(head,-1,sizeof(head));tot=ror=sign=0; } inline void add(int u,int v,ll w) {e[tot].to=v,e[tot].next=head[u],e[tot].w=w,head[u]=tot++; } /*-----------主席樹-----------*/ inline int build(ll l,ll r) {int cur=++ror;p[cur].num=p[cur].sum=0;if(l==r) return cur;ll mid=l+r>>1ll;p[cur].l=build(l,mid);p[cur].r=build(mid+1ll,r);return cur; } inline int update(int rot,ll l,ll r,ll pos) {int cur=++ror;p[cur]=p[rot];p[cur].num++;p[cur].sum+=pos;if(l==r) return cur;ll mid=l+r>>1;if(pos<=mid) p[cur].l=update(p[rot].l,l,mid,pos);else p[cur].r=update(p[rot].r,mid+1ll,r,pos);return cur; } inline void query(int lrot,int rrot,ll &cnt,ll &sum,ll pos,ll l,ll r) {if(l>=pos){cnt+=(p[rrot].num-p[lrot].num);sum+=(p[rrot].sum-p[lrot].sum);return ;}ll mid=l+r>>1;if(pos>mid) query(p[lrot].r,p[rrot].r,cnt,sum,pos,mid+1,r);else{cnt+=(p[p[rrot].r].num-p[p[lrot].r].num);sum+=(p[p[rrot].r].sum-p[p[lrot].r].sum);query(p[lrot].l,p[rrot].l,cnt,sum,pos,l,mid);} } /*----------dfs----------*/ inline void dfs(int u,int f) {in[u]=++sign;root[sign]=update(root[sign-1],1ll,(ll)1e11,dis[u]);//根據(jù)時(shí)間戳建立主席樹for(int i=head[u];i!=-1;i=e[i].next){int to=e[i].to;if(to==f) continue;dis[to]=dis[u]+e[i].w;dfs(to,u);}out[u]=sign; } int main() {int x;ll y;while(~scanf("%d",&n)){init();for(int i=2;i<=n;i++){scanf("%d%lld",&x,&y);add(i,x,y),add(x,i,y);}dis[1]=0;dfs(1,0);scanf("%d",&m);while(m--){scanf("%d%lld",&x,&y);y=dis[x]+y;ll sum_num=0,sum_dis=0;query(root[in[x]-1],root[out[x]],sum_num,sum_dis,y,1ll,(ll)1e11);printf("%lld\n",sum_dis-sum_num*dis[x]);}}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的树的距离（牛客网树上主席树+dfs序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。