傳送門
文章目錄
題意：
給你一棵樹，每個點都有一個權值valvalval，求滿足以下條件
(1)x!=yx!=yx!=y
(2)xxx和yyy不互為祖先
(3)val[lca(x,y)]?2=val[x]+val[y]val[lca(x,y)]*2=val[x]+val[y]val[lca(x,y)]?2=val[x]+val[y]
(4)len(x,y)<=klen(x,y)<=klen(x,y)<=k
求(x,y)(x,y)(x,y)的對數。
思路：
可以發現這個點對是可以轉換成一顆子樹的問題來遞歸解決的，他們以這個子樹的根為lcalcalca，讓后兩個點一定存在于子樹的不同分支里面，碰到子樹問題我們自然的想到用dsudsudsu來解決。
當我們要更新一顆子樹的時候，當前子樹的重兒子的信息已經存起來了，我們只需要依次遍歷計算其他分支，讓后更新其他分支的信息。要注意必須先遍歷計算才能更新，這樣才能保證算出來的一定是根的不同分支里的對數。讓后還有一個問題，就是怎么算答案呢？我們更新的時候是將depth[u]depth[u]depth[u]和val[u]val[u]val[u]一起放到要更新的數組里面的，我們查詢的時候要查詢權值為val[rt]?2?val[now]val[rt]*2-val[now]val[rt]?2?val[now]且深度<=depth[rt]+k?(depth[now]?depth[rt])<=depth[rt]+k-(depth[now]-depth[rt])<=depth[rt]+k?(depth[now]?depth[rt])的點對。顯然普通數據結構不好維護，所以我們可以對每個權值開一顆權值線段樹，讓后動態開點就好啦，就是有點不好調。
最后答案乘二即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<LL
,LL
> PII
;const int N
=200010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,k
;
vector
<int>v
[N
];
int val
[N
];
LL cnt
,ans
[N
];
int depth
[N
],se
[N
],son
[N
];
int root
[N
],idx
;
struct Node
{int l
,r
;int cnt
;
}tr
[N
*40];void modify(int &rt
,int l
,int r
,int x
,int tag
)
{if(!rt
) rt
=++idx
;if(l
==r
) { tr
[rt
].cnt
+=tag
; return; }int mid
=l
+r
>>1;if(x
<=mid
) modify(tr
[rt
].l
,l
,mid
,x
,tag
);else modify(tr
[rt
].r
,mid
+1,r
,x
,tag
);tr
[rt
].cnt
=tr
[tr
[rt
].l
].cnt
+tr
[tr
[rt
].r
].cnt
;
}int query(int rt
,int l
,int r
,int ql
,int qr
)
{if(!rt
) return 0;if(l
>=ql
&&r
<=qr
) return tr
[rt
].cnt
;int mid
=l
+r
>>1;int ans
=0;if(ql
<=mid
) ans
+=query(tr
[rt
].l
,l
,mid
,ql
,qr
);if(qr
>mid
) ans
+=query(tr
[rt
].r
,mid
+1,r
,ql
,qr
);return ans
;
}void dfs_son(int u
,int fa
)
{se
[u
]=1; depth
[u
]=depth
[fa
]+1;for(auto x
:v
[u
]){if(x
==fa
) continue;dfs_son(x
,u
);se
[u
]+=se
[x
];if(se
[x
]>se
[son
[u
]]) son
[u
]=x
;}
}void update(int u
,int fa
,int son
,int tag
)
{modify(root
[val
[u
]],1,n
,depth
[u
],tag
);for(auto x
:v
[u
]){if(x
==fa
||x
==son
) continue;update(x
,u
,son
,tag
);}
}void solve(int u
,int fa
,int son
,int rt
)
{if(val
[rt
]*2-val
[u
]>=0&&val
[rt
]*2-val
[u
]<=n
&&depth
[rt
]+k
-(depth
[u
]-depth
[rt
])>=depth
[rt
]+1) cnt
+=query(root
[val
[rt
]*2-val
[u
]],1,n
,depth
[rt
]+1,min(depth
[rt
]+k
-(depth
[u
]-depth
[rt
]),n
));for(auto x
:v
[u
]){if(x
==fa
||x
==son
) continue;solve(x
,u
,son
,rt
);}
}void dfs(int u
,int fa
,int op
)
{for(auto x
:v
[u
]){if(x
==fa
||x
==son
[u
]) continue;dfs(x
,u
,0);}if(son
[u
]) dfs(son
[u
],u
,1);for(auto x
:v
[u
]){if(x
==fa
||x
==son
[u
]) continue;solve(x
,u
,son
[u
],u
); update(x
,u
,son
[u
],1);}modify(root
[val
[u
]],1,n
,depth
[u
],1);ans
[u
]=cnt
; cnt
=0;if(!op
) update(u
,fa
,-1,-1);
}int main()
{
scanf("%d%d",&n
,&k
);for(int i
=1;i
<=n
;i
++) scanf("%d",&val
[i
]);for(int i
=2;i
<=n
;i
++){int x
; scanf("%d",&x
);v
[x
].pb(i
);}dfs_son(1,0);dfs(1,0,1);LL sum
=0;for(int i
=1;i
<=n
;i
++) sum
+=ans
[i
];printf("%lld\n",sum
*2);return 0;
}
總結
以上是生活随笔為你收集整理的2019 ICPC Asia Nanchang Regional K.Tree 树上启发式合并 + 动态开点线段树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
