hdu-544 Happy King

件名:
n個の結点の木を与え、その上に価値がある.
点対(x,y)を求めてxを満たします!=yかつxからyへの経路上の最大値と最小値の差<=D;
n<=100000、複数グループのデータ、すべてのデータnの合計<=500000;
クイズ:
その年に掘った穴を埋めるために来ました.
このデータ範囲は本当に悪意です.直接5組のデータを言うのはよくないですか?
この問題をどうするかを考えて、この試験の日の前の日に、木の分治アルゴリズムを勉強しました.
それから彼が出てきて、私は書きました.そして私は書けませんでした.
当時の私は本当にnaiveです.
私は当時提出したコードを引き出して、長い間変更しました.
まずこの問題は考え方が簡単です.一番直観的なのは木のポイントを分けます.
分割した後に解答を統計して、まず現在のルートからすべての点の最大の権利と最小の権利を探し出します.
それから、数量を統計するために、まず最大の権利値で小さい時から大きな順に並べます.
もしこの最大の権利を道中の最大の権利とするならば、他の端点はきっとその前に並べられます.
したがって、点の最小値をツリー配列にエルゴードしながら挿入します.
毎回[0,点からルートの最大値-D]という区間の値を調べたらいいです.
複雑度O(nlog^2 n)、他の人はもっと優れたlogsのやり方があります.
口がいいAですよね.でも、本当に助けられませんでした.
毎回重心を求めていますが、重心で治療していませんでした.
この二つのコードの違いはアルファベット一つの違いです.そして複雑さが違っています.
コード:

#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#define N 100100
using namespace std;
typedef long long ll;
struct pr
{
	int ma,mi;
	friend bool operator >1;
		if(dis[mid]D)	return ;
    ma=max(ma,val[x]);
    mi=min(mi,val[x]);
    static pr p;
    p.ma=ma,p.mi=mi;
    popo[++cnt]=p;
    int i,y;
    for(i=head[x];i;i=nex[i])
    {
        if(!ban[y=to[i]]&&y!=pre)
        {
            dfs(y,x,ma,mi);
        }
    }
}
ll calc(int x)
{
	static pr p;
	p.ma=p.mi=val[x];
    popo[cnt=1]=p;
    int i,j,y,last;
    ll ret=0;
    for(j=head[x];j;j=nex[j])
    {
        if(!ban[y=to[j]])
        {
            last=cnt;
            dfs(y,x,val[x],val[x]);
            sort(popo+last+1,popo+cnt+1);
            for(i=last+1;i<=cnt;i++)
            {
				if(popo[i].ma-popo[i].mi<=D)
                ret+=i-last-1-query(lb(popo[i].ma-D)-1);
                update(lb(popo[i].mi),1);
            }
            for(i=last+1;i<=cnt;i++)
                update(lb(popo[i].mi),-1);
        }
    }
    ret=-ret;
    sort(popo+1,popo+cnt+1);
    for(i=1;i<=cnt;i++)
    {
    	if(popo[i].ma-popo[i].mi<=D)
        ret+=i-1-query(lb(popo[i].ma-D)-1);
        update(lb(popo[i].mi),1);
    }
    for(i=1;i<=cnt;i++)
        update(lb(popo[i].mi),-1);
    return ret;
}
void slove(int x)
{
    ban[x]=1;
    if(bk==1)	{ban[x]=0;return ;}
    int i,y;
    for(i=head[x];i;i=nex[i])
    {
        if(!ban[y=to[i]])
        {
            bk=size[y];
            mi=0x3f3f3f3f;
            get_G(y,x);
            slove(G);
        }
    }
	ans+=calc(x);
	ban[x]=0;
}
int main()
{
//	freopen("tt.in","r",stdin);
    int c,T,n,m,i,j,k,x,y;
    T=read();
    for(c=1;c<=T;c++)
    {
        init();
        n=read(),D=read();
        for(i=1;i<=n;i++)
        {
        	val[i]=read();
            dis[i]=val[i];
        }
        sort(dis+1,dis+n+1);
        len=unique(dis+1,dis+n+1)-dis-1;
        for(i=1;i