题目大意：给一棵树，每条边有两个权值ai和bi，
当路径上sigma(ai)和sigma(bi)都不超过限制la,lb时，点对(i,j)可达，
求不可达的无序点对(i,j)的数量。
数据范围：N<=10^5，ai,bi<=10^9，la,lb<=10^14
题解：树上的路径问题，这次树形dp无法解决这道题了，
于是考虑利用树分治解决树上路径问题，
每次找出重心进行树分治后，
如果对a,b用二维数据结构强行维护，可以O(nlog^3n)解决，
然而这样不仅代码复杂度高，而且会被某出题人无情卡T，
因为有两个log后面的数字达到了10^14 。
再考虑一些更加巧妙的办法-------->
离线后，扫描线+树状数组维护，
对于每个点， 通过树分治后的扫描(树形dp)， 我们得到了三个特征值：ai,bi,ci，
其中，ai,bi分别表示到根节点的a,b两种权值的权值和，ci表示这个点所在的子树，
这个点的询问是(la-ai,lb-bi,c),就是满足aj<=la-ai,bj<=lb-bi,cj!=ci的j的个数，
将每个点产生的三元组先进行离散化，
然后它们进行排序后利用树状数组进行询问，
树状数组维护时，维护一个总体的树状数组，对于每个颜色再维护一个树状数组，
计算答案时，对两个树状数组分别询问后作差即为对答案的贡献，
注意，因为ci可能达到O(n)种，所以树状数组要用vector开。
然后，就可以得到一个常数很小的O(nlog^2n)的树分治+离线后扫描线,离散化+树状数组的解法。
Code:
#include <bits/stdc++.h> #define ll long long using namespace std; ll x[100005],y[100005],lx,ly,ans=0; int head[100005],nxt[200005],v[200005],tot=0; int ntp,cnt=0; ll w1[200005],w2[200005]; ll dx[100005],dy[100005]; bool vis[100005]; int maxn[100005],sz[100005],n,rt,minn=1000000,mpos=-1; struct node {int typ,c; ll x,y; }q[200005]; inline bool cmp(node a,node b) {if (a.x!=b.x) {return a.x<b.x;} if (a.y!=b.y) {return a.y<b.y;} return a.typ<b.typ; } struct fenwick {vector <ll> t; vector <ll> a; void clear() {t.clear(); a.clear(); } void add(ll x) {a.push_back(x); } void init() {sort(a.begin(),a.end()); t.assign(a.size()+1,0); } void update (ll x) {int pos=(lower_bound(a.begin(),a.end(),x)-a.begin()); pos++; while (pos<=a.size()+1) {t[pos]++; pos+=(pos&(-pos)); } } ll query (ll val) {int pos=(lower_bound(a.begin(),a.end(),val)-a.begin()); pos++; ll s=0; while (pos) {s+=t[pos]; pos-=(pos&(-pos)); } return s; } }f[100005]; inline ll my_abs(ll a) {if (a<0) return -a; return a; } inline void add(int a,int b,ll v1,ll v2) {tot++; nxt[tot]=head[a]; head[a]=tot; v[tot]=b; w1[tot]=v1; w2[tot]=v2; } void dfs1(int pos,int fa) {sz[pos]=1;maxn[pos]=0; for (int i=head[pos];i;i=nxt[i]) {if (v[i]!=fa&&!vis[v[i]]) {dfs1(v[i],pos); sz[pos]+=sz[v[i]]; maxn[pos]=max(maxn[pos],sz[v[i]]); } } } void dfs2(int pos,int fa) {maxn[pos]=max(maxn[pos],sz[rt]-sz[pos]); if (maxn[pos]<minn) {minn=maxn[pos];mpos=pos;} for (int i=head[pos];i;i=nxt[i]) {if (v[i]!=fa&&!vis[v[i]]) {dfs2(v[i],pos);} } } void dp(int pos,int fa,int typ) {cnt++; q[cnt].typ=1; q[cnt].c=typ; q[cnt].x=dx[pos]; q[cnt].y=dy[pos]; f[typ].add(dy[pos]); f[0].add(dy[pos]); cnt++; q[cnt].typ=2; q[cnt].c=typ; q[cnt].x=lx-dx[pos]; q[cnt].y=ly-dy[pos]; f[typ].add(ly-dy[pos]); f[0].add(ly-dy[pos]); for (int i=head[pos];i;i=nxt[i]) {if (!vis[v[i]]&&v[i]!=fa) {if (!fa) {typ=++ntp; f[ntp].clear(); } dx[v[i]]=dx[pos]+w1[i]; dy[v[i]]=dy[pos]+w2[i]; dp(v[i],pos,typ); } } } void solve(int pos) {int i; rt=pos; minn=1000000; mpos=-1; dfs1(pos,0); dfs2(pos,0); vis[mpos]=1; dx[mpos]=0; dy[mpos]=0; ntp=0;cnt=0; f[0].clear(); dp(mpos,0,0); for (i=0;i<=ntp;i++) {f[i].init();} sort(q+1,q+cnt+1,cmp); for (i=1;i<=cnt;i++) {if (q[i].typ==1) {if (q[i].c) {f[q[i].c].update(q[i].y);} f[0].update(q[i].y); } else {ans+=f[0].query(q[i].y); if (q[i].c) {ans-=f[q[i].c].query(q[i].y);} } } ans--; for (i=head[mpos];i;i=nxt[i]) {if (!vis[v[i]]) {solve(v[i]);} } return; } int main (){ int i,u,v; scanf ("%d",&n); scanf ("%lld%lld",&lx,&ly); for (i=1;i<=n;i++) {scanf ("%lld%lld",&x[i],&y[i]);} for (i=1;i<n;i++) {scanf ("%d%d",&u,&v); ll delx=my_abs(x[u]-x[v]); ll dely=my_abs(y[u]-y[v]); add(u,v,delx,dely); add(v,u,delx,dely); } solve(1); ans=(((ll)(n))*((ll)(n-1)))-ans; ans/=2ll; printf ("%lld\n",ans); return 0; }
