题解 P4281 【[AHOI2008]紧急集合 / 聚会】

蒟蒻最近刚学会树链剖分，想找些模板题来~~水积分~~练习下。 然后我就找到了这一题。 作为一个无脑数据结构选手，拿到题的第一件事就是看~~题解~~数据范围。 ## N<=500000，M<=500000 GG...莫非还有O(NlogN)的树剖？ 树剖常熟小,跑不满！ 怀着一种常数的信仰，我们开始解题： ------------ 首先看到题中给的图是一棵树~~废话~~ 然后看到多次给出树上的三个点 把一个点移动经过一条边需要花费1~~节操~~游戏币 求把三个点移动到一起最少需要多少游戏币 ~~易~~发现这个最优的集合点一定在这三个点互相通达的简单路径上 可能有点难理解(能感性理解的请跳过分界线) 比如这图,e是简单路径外一点 简单路径: ``` . / / / . ``` 简单路径外一点e: ``` . / /\ / \ . e ``` 这三个点想要到达e点，必须先要来到a点。因为这是一棵树，这三个点到e只分别存在一条道路，三个点能到达a，通过a就能分别到达e，如果~~破壁者~~有另一条道路的话，这就不是树了 a: ``` . / a / \ / \ . e ``` 想要到达e点，必须先要来到a点。 很明显，e点比a点劣(既然已经来到a点不如就在a点集合算了)。 这就证明了最优的集合点一定在这三个点互相通达的简单路径上。 ------------ 上图 a,b,c分别表示三个点 简单路径如图 ``` . / \ / \ / \ \ / \ c a b ``` 通过~~大眼观察法~~，很容易发现$LCA(a,c)==LCA(b,c)$ 在树上任选三点t1,t2,t3 $LCA(t1,t2),LCA(t1,t3),LCA(t2,t3)$中一定有两个是相等的。 相信大家都能理解，不能理解的手动模拟一下 上面的图拉直，大概长这样 ``` c | | | | / \ / \ a b ``` 很明显了,这三条线段的唯一公共点w就是最优集合地！！！ ``` c | | | | w / \ / \ a b ``` 证明的话还是用反证法(同上，能感性理解的请跳过分界线) 设有一点h不在w处，却比w优(暂且让他待在CW边上，其他的情况把图转一转就好了) ``` c | | h | w / \ / \ a b ``` 拿出初一几何的架势来(~~其他的不会，我才新初二~~)！！ $Cost_h=CH+(AW+WH)+(BW+WH)=(CH+WH)+AW+BW+WH=CW+AW+BW+WH$ 原先选择w点的花费$Cost_w=CW+AW+BW$ 很明显$Cost_h-Cost_w=WH$ 而$WH>0$，所以取点h一定比点w劣 ------------ 看回原图： ``` . / \ / \ / \ \ / \ c a b ``` w点在这里： ``` . / \ / \ w \ / \ \ / \ c a b ``` 很明显，w是$LCA(a,b),LCA(a,c),LCA(b,c)$中深度最大的那一个。 相信大家都能理解(~~真的很明显~~) 然后就可以愉快地套板子了~~哈哈哈哈哈哈~~... ------------ $LCA$：已经写了链剖了，就没倍增什么事了 统计$CW+AW+BW$：链剖中的两点间路径统计 完美，接下来就是~~码码码码农~~ ## NO,Stop！！！ 这题不带修！ 题不带修！ 不带修！ 带修！ 修！ ## 根据套路，不带修的树剖都能用倍增解决 这题也是如此 倍增求某个点深度，某两个点的$LCA$,简单的一匹。 . 下面是~~愉快的~~分类讨论时间 设三个点为$t1,t2,t3;$三个点的深度为$d1,d2,d3$。 如果$w=LCA(a,b)$最深 ``` . / \ / \ w \ / \ \ / \ c a b ``` 答案为$deep(a)-deep(w)+deep(b)-deep(w)+deep(c)-deep(.)+deep(w)-deep(.)$ 整理得$deep(a)+deep(b)+deep(c)-deep(w)-deep(.)-deep(.)$ 如果$w=LCA(a,c)$最深(我不推那么细了) ``` . / \ / \ w \ / \ \ / \ b a c ``` 答案还是为$deep(a)+deep(b)+deep(c)-deep(w)-deep(.)-deep(.)$ 如果$w=LCA(c,b)$最深(我不推那么细了) ``` . / \ / \ w \ / \ \ / \ a c b ``` 答案依旧为$deep(a)+deep(b)+deep(c)-deep(w)-deep(.)-deep(.)$ 综上所述，答案为 $deep(a)+deep(b)+deep(c)-$最**深**$LCA$的深度$-$最**浅**$LCA$的深度$*2$ 此题完结 代码： ```cpp // luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<vector> #include<cctype> using namespace std; int n,t1,t2,t3,q,len,d1,d2,d3,u1,u2,u3, f[520500][20],t[520500]; vector<int> g[520500]; bool e[520500]; inline int read() { int X=0; char ch=0,w=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; }//快速读入 int getdeep(int num) { int k=18,ans=0; while(k>=0){ while(f[num][k]) {num=f[num][k];ans+=1<<k;} k--; }return ans; }//求某个点的深度 int lca(int x,int y) { int k,dx,dy; dx=getdeep(x);dy=getdeep(y); if (dx>dy){swap(dx,dy);swap(x,y);} k=18; while(k>=0){ while(dy-dx>=(1<<k)) {y=f[y][k];dy-=1<<k;} k--; }k=18; while(k>=0){ while(f[x][k]!=f[y][k]) {x=f[x][k];y=f[y][k];} k--; } if (x!=y)x=f[x][0]; return x; }//求某两个点的LCA void dfs(int num) { e[num]=1; for (int i=0;i<g[num].size();i++) if (e[g[num][i]]) f[num][0]=g[num][i]; else dfs(g[num][i]); }//化无向为有向 int main() { n=read();q=read(); for (int i=1;i<n;i++){ t1=read();t2=read(); g[t1].push_back(t2); g[t2].push_back(t1); }dfs(1); //--------建图-------- for (register int j=1;j<=18;j++) for (register int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; //--------倍增预处理-------- for (int i=1;i<=q;i++){ t1=read();t2=read();t3=read(); u1=lca(t1,t2); u2=lca(t2,t3); u3=lca(t1,t3); d1=getdeep(u1); d2=getdeep(u2); d3=getdeep(u3); if (d1==d2) printf("%d ",u3); else if (d3==d2) printf("%d ",u1); else printf("%d ",u2); printf("%d\n",getdeep(t1)+getdeep(t2)+getdeep(t3) -min(d1,min(d2,d3))*2-max(d1,max(d2,d3))); } return 0; } ``` 代码略丑，各位dalao请见谅