ICPC 2019 Hong Kong C（点分治）

[题目链接](https://vjudge.net/problem/Gym-102452C) ------------ 对于树上的一条简单路径$<x,y>$，路径上的权值和为$sum$，路径上权值最大值为$mx$ 能够构成多边形的充要条件为$sum-mx>mx$，即$sum>2 *mx$ 考虑点分治 令$sum_{i}$为点 $i$ 到树的重心$t$的路径权值和，$mx_i$为路径上权值最大值，$a_t$为重心的权值 那么经过重心$t$且满足条件的路径$<x,y>$满足：$sum_x+sum_y-a_t>2*max(mx_x,mx_y)$ 对当前要处理的所有点按$mx_i$从小到大排序，然后通过二分$+$树状数组计算 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M=2e5+5; int n,a[M],siz[M],mxsiz[M],rt,rtsiz,vis[M],c[M],m; ll ans; vector< pair<int,ll> > v; vector<ll> s; vector<int> vt[M]; void getroot(int x,int fa) { siz[x]=1; mxsiz[x]=0; for(auto y:vt[x]) { if(vis[y]||y==fa)continue; getroot(y,x); siz[x]+=siz[y]; mxsiz[x]=max(mxsiz[x],siz[y]); } mxsiz[x]=max(mxsiz[x],rtsiz-mxsiz[x]); if(mxsiz[x]<mxsiz[rt])rt=x; } void getval(int x,int fa,int mx,ll sum) { v.push_back(make_pair(mx,sum)); for(auto y:vt[x]) { if(y==fa||vis[y])continue; getval(y,x,max(mx,a[y]),sum+a[y]); } } int lowbit(int x) {return x&(-x);} void upd(int pos,int x){for(int i=pos;i<=m;i+=lowbit(i))c[i]+=x;} int que(int pos){int res=0;for(int i=pos;i;i-=lowbit(i))res+=c[i];return res;} ll calc(int x,ll d) { v.clear();s.clear(); getval(x,0,max(a[x],(int)d),d+a[x]); sort(v.begin(),v.end()); for(auto p:v)s.push_back(p.second); sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end()); m=s.size(); for(int i=1;i<=m;i++)c[i]=0; d=(d?d:a[x]); ll res=0; int cnt=0; for(auto p:v) { int pos=upper_bound(s.begin(),s.end(),2*p.first+d-p.second)-s.begin(); res+=cnt-que(pos); int k=lower_bound(s.begin(),s.end(),p.second)-s.begin()+1; upd(k,1); cnt++; } return res; } void solve(int x) { vis[x]=1; ans+=calc(x,0); for(auto y:vt[x]) { if(vis[y])continue; ans-=calc(y,a[x]); rt=0; mxsiz[0]=rtsiz=siz[y]; getroot(y,x); solve(rt); } } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); ans=0; for(int i=1;i<=n;i++)vis[i]=0,vt[i].clear(); for(int i=1;i<=n-1;i++) { int x,y;scanf("%d%d",&x,&y); vt[x].push_back(y); vt[y].push_back(x); } rt=0; mxsiz[0]=rtsiz=n; getroot(1,0); solve(rt); printf("%lld\n",ans); } return 0; } ```