[BZOJ1316 树上的询问]关于树的基于点的划分

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1316
【解题经历】
其实我做这题是有一段曲折的经历的。。。
第一次见面是由于师傅在ACM_DIY群里说在衡阳八中的OJ上见到了ACRush。。。于是果断跑过去围观。
一看~晕，用PASCAL的ACRush。。。假。。。
然后围观他做的那题——就是本题了。。。
于是我苦思冥想~最终没有任何想法，果断GG。。。
然后后来由于我想做男人…于是围观了漆大神的论文,YY了一下,把树上基于点的分治领悟了一下.
然后就把男人八题里相关的那题AC了.今日突然想起这题.再次来围观,额,终于有想法了.
然后一开始WA到SB。
写了个朴素来随机对拍。没错啊~= =
然后猛然发现如果他给出的长度是0，是必须Yes的。而我的是No。
改完一交，TLE。。。万念俱灭啊。。。
然后回去做了一节晚修的作业，突然有灵感，上来一改，果然AC。还排第二，不错呢。
【算法分析】
先将树根据点的数量分割，分成很多份（有点像线段树），然后再从小份的到大份的弄回来处理。
分割复杂度：O(N lg N)
处理的话就直接枚举给出的LEN。一个一个分开判断，然后在判的时候排一下序，
排这个序的总复杂度变成O(N lg^2 N)。
利用单调性可以做到O(Qt) per 分割树节点的复杂度。其中Qt表示该分割树区间的点的数量。

然后我们来围观一下TLE的原因：
我把枚举给出的询问放在solve的外面，于是复杂度变成O(QN lg^2 N) 其中Q为询问个数。
于是，
我们把枚举给出的询问放在solve的排序后面，复杂度就变成O(N lg^2 N+QN lg N)。
于是终于AC!
【其他】
好弱啊。。。YM GP大神。
大家也可以去围观提交记录，确实是ACRush在提交。。。表示没有撒谎~
另外程序中的big是因为有一段时间WA到不行，全部改成long long了。
后来改回来就继续用big了~
【CODE】
#include #include #include #include #include using namespace std;
typedef int big;
const big N=10005;
const big INF=0x7FFFFFFF;
struct edge{big x,y;big c;edge *next;}g[2*N],*ls[N];
struct PobigType{big dep,l,r,root;}tr[N*20];
big n,Qn,e,PN,Qt,CT;
big pl[20][N],color[20][N],size[N],tot[20],Q[N];
big dis[N],Que[N];
bool result[N];

void add(big x,big y,big c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e];
}

void input(){
e=0;
for (big i=1;i<=n;i++) ls[i]=NULL;
scanf("%d%d",&n,&Qn);
big x,y,c;
for (big i=1;i scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
add(y,x,c);
}
memset(tot,0,sizeof(tot));
PN=1; CT=1;
for (big i=1;i<=n;i++) pl[1][i]=i;
}

void makelabel(big p,big fa,big &times,big *co){
size[p]=times++;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[t->y]==co[p]){
dis[t->y]=dis[p]+t->c;
makelabel(t->y,p,times,co);
}
size[p]=times-size[p];
}

void choose_root(big p,big fa,big *co,big &root,big &cost,big &total){
big NowCost=total-size[p];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[t->y]==co[p]) NowCost=max(NowCost,size[t->y]);
if (NowCost cost=NowCost;
root=p;
}
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[t->y]==co[p])
choose_root(t->y,p,co,root,cost,total);
}

void AddPoint(big p,big fa,big *PL,big &TOT,big *co){
PL[++TOT]=p;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa && co[p]==co[t->y])
AddPoint(t->y,p,PL,TOT,co);
}

void Div(big pos,big l,big r,big dep){
PobigType *p=&tr[pos];
big times=0,cost=INF,i,*co=color[dep];
p->l=l; p->r=r; p->dep=dep;
for (i=l;i<=r;i++) co[pl[dep][i]]=CT;
if (l>=r){
PN–;
return;
}
dis[l]]=0;
makelabel(pl[dep][l],0,times,co);
choose_root(pl[dep][l],0,co,p->root,cost,size[l]]);
for (edge *t=ls[p->root];t;t=t->next)
if (co[t->y]==co[p->root]){
big L=tot[dep+1]+1;
AddPoint(t->y,p->root,pl[dep+1],tot[dep+1],co);
big R=tot[dep+1];
PN++; CT++;
Div(PN,L,R,dep+1);
}
}

inline bool Qcmp(int x,int y){
return dis[x]}

void solve(){
for (big pos=PN;pos>=1;pos–){
PobigType *p=&tr[pos];
big times=0;
dis[p->root]=0;
makelabel(p->root,0,times,color[p->dep]);
Qt=0;
for (big i=p->l;i<=p->r;i++)
Q[++Qt]=pl[p->dep][i];
sort(Q+1,Q+Qt+1,Qcmp);
for (big k=1;k<=Qn;k++) if (!result[k]){
big ans=Que[k],j=0;
for (big i=1;i<=Qt;i++){
if (dis[Q[i]]>ans) break;
while (j+1 while (j && dis[Q[j]]+dis[Q[i]]>ans) j–;
while (j && color[p->dep+1][Q[j]]==color[p->dep+1][Q[i]]) j–;
if (j && dis[Q[j]]+dis[Q[i]]==ans){
result[k]=true;
break;
}
}
}
}
}