前言：
(Point~divide~and~rule)
使用
淀粉质就是在树上，依靠不停的递归和分治，解决相同的子问题
先来看看模板题: (Tree)
就是找树上(<=K)的路径有多少
我们可以分两种情况讨论
(1.) 经过根节点(p)的路径
(2.) 不经过根节点(p)的路径
第二种情况可以通过递归来处理，我们直接来讨论第一种情况
设当前的树根节点为 (p)
显然一条经过(p)路径可以由两条到端点为(p)的链组成
显然，会出现重复的情况，例如:
(好大...
这两条链组成的已经不是一条路径了，我们需要去除这种非法情况，这里提供两种方法
(1.)容斥
我们只需要统计(p)树内子节点到(p)的距离，排序后，用双指针做,再把(p)子节点的非法情况用种方法去除
(2.~treap)，强烈安利---(fhq-treap)
我们只需要把(p)树的子树依次处理，对于(p)的一棵子树(y),先把所有在(y)树里的路径长度(Dis)统计出来，再在(treap)里找(<=K-Dis)的个数,最后将这些路径放入(treap)
(推荐使用这一种，一般来说大多数题目都需要不用(treap)，暴力开桶就行了，这种技巧十分重要
这两种方法都要会掌握
统计完成了，那我们怎么递归呢?
这里有一个核心，我们每次选择只选重心来递归，由于中心的子节点(size)永远不会超过(Root~size/2)，所以我们的递归层数不会超过(log(n))
每一次计算是(nlogn),递归层数(log(n)),总时间复杂度是(O(nlognlogn)),巧妙的暴力
(code:)(这里用的是第一种去重方法,太懒了）
#include<bits/stdc++.h>
using namespace std;
const long long N=4e4+10;
struct data {
long long val,stb,to;
} a[N*2];
long long head[N],max_size[N],size[N],vis[N],Root,k,Dis[N],cnt,n,tot,ans,size_sontree;
void insert(long long x,long long y,long long z) {
a[++tot].to=y;
a[tot].stb=head[x];
a[tot].val=z;
head[x]=tot;
}
long long get_root(long long x,long long fa) {
size[x]=1;
max_size[x]=0;
for(long long i=head[x]; i; i=a[i].stb) {
long long xx=a[i].to;
if(xx==fa||vis[xx]) continue;
get_root(xx,x);
size[x]+=size[xx];
max_size[x]=max(max_size[x],size[xx]);
}
max_size[x]=max(max_size[x],size_sontree-size[x]);
if(max_size[x]<max_size[Root]) Root=x;
}
long long find_dis(long long x,long long fa,long long D) {
Dis[++cnt]=D;
for(long long i=head[x]; i; i=a[i].stb) {
long long xx=a[i].to;
if(xx==fa||vis[xx]) continue;
find_dis(xx,x,D+a[i].val);
}
}
long long find_ans(long long x,long long fa,long long D) {
cnt=0;
find_dis(x,0,D);
sort(Dis+1,Dis+cnt+1);
long long l=1,r=cnt,sum=0;
while(1) {
while(Dis[l]+Dis[r]>k&&r) r--;
if(l>r) break;
sum+=r-l;
l++;
}
return sum;
}
void slove(long long x) {
vis[x]=1;
ans+=find_ans(x,0,0);
for(long long i=head[x]; i; i=a[i].stb) {
long long xx=a[i].to;
if(!vis[xx]) {
ans-=find_ans(xx,x,a[i].val);
Root=0;
size_sontree=size[xx];
get_root(xx,x);
slove(Root);
}
}
}
int main() {
scanf("%lld",&n);
for(long long i=1,x,y,z; i<=n-1; i++) {
scanf("%lld%lld%lld",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
}
scanf("%lld",&k);
max_size[0]=INT_MAX;
size_sontree=n;
get_root(1,0);
slove(1);
printf("%lld",ans);
}
其他例题
[Noip模拟题]树上路径
找出最小的(Dis>=S)即可，由于是取最小值，所以容斥就不行了，这里使用的是(set)
(code:)(在线格式化不要嫌丑
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int max_size[N], size_sontree, size[N], head[N], Dis[N], vis[N], Root, tot, cnt, n, S, E, ans;
struct data {
int stb, to, val;
} a[N * 2];
void insert( int x, int y, int z )
{
a[++tot].to = y;
a[tot].stb = head[x];
a[tot].val = z;
head[x] = tot;
}
int get_root( int x, int fa )
{
size[x] = 1, max_size[x] = 0;
for ( int i = head[x]; i; i = a[i].stb )
{
int xx = a[i].to;
if ( xx == fa || vis[xx] )
continue;
get_root( xx, x );
size[x] += size[xx];
max_size[x] = max( max_size[x], size[xx] );
}
max_size[x] = max( max_size[x], size_sontree - size[x] );
/* printf("mxsize[%d]=%d
",x,max_size[x]); */
if ( max_size[x] < max_size[Root] )
Root = x;
}
void find_dis( int x, int fa, int D )
{
Dis[++cnt] = D;
for ( int i = head[x]; i; i = a[i].stb )
{
int xx = a[i].to;
if ( xx == fa || vis[xx] )
continue;
find_dis( xx, x, D + a[i].val );
}
}
int calc( int x )
{
cnt = 0;
set<int>q;
q.insert( 0 );
for ( int i = head[x]; i; i = a[i].stb )
{
int xx = a[i].to;
if ( vis[xx] )
continue;
cnt = 0;
find_dis( xx, x, a[i].val );
for ( int l = 1; l <= cnt; l++ )
{
/* cout<<Dis[l]<<" "; */
set<int>::iterator r = q.lower_bound( S - Dis[l] );
if ( r == q.end() )
continue;
ans = min( ans, Dis[l] + *r );
}
for ( int j = 1; j <= cnt; j++ )
q.insert( Dis[j] );
}
}
void Slove( int x )
{
vis[x] = 1;
calc( x );
/* printf("Root:%d
",x); */
for ( int i = head[x]; i; i = a[i].stb )
{
int xx = a[i].to;
if ( vis[xx] )
continue;
Root = 0;
size_sontree = size[xx];
get_root( xx, x );
Slove( Root );
}
}
int main()
{
ans = INT_MAX;
scanf( "%d%d%d", &n, &S, &E );
for ( int i = 1; i <= n - 1; i++ )
{
int x, y, z;
scanf( "%d%d%d", &x, &y, &z );
insert( x, y, z );
insert( y, x, z );
}
max_size[0] = INT_MAX;
size_sontree = n;
get_root( 1, 0 );
Slove( Root );
if ( ans <= E )
printf( "%d", ans );
else printf( "-1" );
}
[黑白配]（http://www.forioi.com/p/6547）
这里有两个条件:
(1.)路径上黑色边与白色边的数量相同。
(2.)路径中存在一个不同于起始点和终点的点，它到终点的路径也满足(1)。
把黑看成(1)，白看成(-1),两条链的(Dis)为相反数即可满足(1)条件
讨论第二种条件：
如果一条链(p->u)的(Dis)在这条链中间任意一点(p->v)的(Dis)也出现过，那么(u->v)的(Dis)就为(0)，我们称这条链为(can)链，
处理(can)链可以用递归来做，开个(map)统计(Dis)的出现
我们发现，只要两条链只要有一条(can)链，就能满足条件(2)，开两个(2维map)来统计(can链)和非(can链)的个数，用类似第二种情况去重,还需要特判单独一条链的情况
(code:)(此题细节较多)
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6 + 10;
long long max_size[N], size_sontree, size[N], head[N], Dis[N], vis[N], Root, tot, cnt, n, S, E, ans, use[N];
map<long long, long long > duck;
map<long long, long long > mp1;
map<long long, long long > mp0;
struct data {
long long stb, to, val;
} a[N * 2];
void insert( long long x, long long y, long long z )
{
a[++tot].to = y;
a[tot].stb = head[x];
a[tot].val = z;
head[x] = tot;
}
long long get_root( long long x, long long fa )
{
size[x] = 1, max_size[x] = 0;
for ( long long i = head[x]; i; i = a[i].stb )
{
long long xx = a[i].to;
if ( xx == fa || vis[xx] )
continue;
get_root( xx, x );
size[x] += size[xx];
max_size[x] = max( max_size[x], size[xx] );
}
max_size[x] = max( max_size[x], size_sontree - size[x] );
if ( max_size[x] < max_size[Root] )
Root = x;
}
void find_dis( long long x, long long fa, long long D )
{
Dis[++cnt] = D;
if ( duck[D] )
{
if ( D == 0 && duck[0] != 1e6 )
ans++;
use[cnt] = 1;
}
duck[D]++;
for ( long long i = head[x]; i; i = a[i].stb )
{
long long xx = a[i].to;
if ( xx == fa || vis[xx] )
continue;
find_dis( xx, x, D + a[i].val );
}
duck[D]--;
}
long long calc( long long x )
{
cnt = 0;
int last = 0;
for ( long long i = head[x]; i; i = a[i].stb )
{
long long xx = a[i].to;
if ( vis[xx] )
continue;
duck[0] = 1e6;
find_dis( xx, x, a[i].val );
for ( long long l = last + 1; l <= cnt; l++ )
{
ans += mp1[-Dis[l]];
if ( use[l] )
ans += mp0[-Dis[l]];
}
for ( long long l = last + 1; l <= cnt; l++ )
{
if ( use[l] )
mp1[Dis[l]]++;
else mp0[Dis[l]]++;
}
last = cnt;
}
for ( long long l = 1; l <= cnt; l++ )
{
if ( use[l] )
mp1[Dis[l]]--, use[l]--;
else mp0[Dis[l]]--;
}
}
void Slove( long long x )
{
vis[x] = 1;
calc( x );
for ( long long i = head[x]; i; i = a[i].stb )
{
long long xx = a[i].to;
if ( vis[xx] )
continue;
Root = 0;
size_sontree = size[xx];
get_root( xx, x );
Slove( Root );
}
}
int main()
{
scanf( "%lld", &n );
for ( long long i = 1; i <= n - 1; i++ )
{
long long x, y, z;
scanf( "%lld%lld%lld", &x, &y, &z );
if ( z == 0 )
z = -1;
insert( x, y, z );
insert( y, x, z );
}
max_size[0] = INT_MAX;
size_sontree = n;
get_root( 1, 0 );
Slove( Root );
printf( "%lld", ans );
}
总结:
其他的直接套模板，主要是去重
(1.)找路径<=(K),用容斥
(2.)找路径(=K)，暴力用桶
(3.)找最值，用(set)
(fhq-treap)并没卵用
完结撒花