題目鏈接：
擒賊先擒王，每次賽後總結CF的題，我都喜歡先搞E題，而且E題一般是我最愛的數據結構題，搞起來特爽
E題：給你一棵樹，求滿足距離之和<=L 且 路徑上的權值之和<= w的點對數量。。。
方法是點的分治，具體參考漆子超的論文，分治算法在樹的路徑中的應用，論文裡面已經講了很詳細了
會了poj 1741的話，其實這道題就是多了一個限制，還是排序，掃描，不過在求的時候需要用樹狀數組維護一下，其實很簡單，不過我還是調試了很久，，，，，代碼能力與思維能力都需要精雕細琢啊。
在求一個二元組序列有多少對滿足條件時卡了很久，看大神們都是加了一個0 0進去，我就是不想加，於是越寫越煩，不是少算就是多算，最後冷靜下來重新想了想，那還是先算成兩倍的吧
我的那個calc函數略挫，，，，
poj 1741
[cpp]
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100010;
struct Edge{
int b , w;
Edge() {}
Edge(int b,int w): b(b),w(w){
}
};
#define Tr(it,x) for(vector<Edge>::iterator it = x.begin(); it!=x.end();it++)
vector<Edge> edge[MAX_N];
int N , K;
int size[MAX_N] ;
int opt[MAX_N];
bool del[MAX_N] ;
long long Ans ;
vector<int> tnode;
void Dfs(int u,int fa)
{
tnode.push_back(u);
opt[u] = 0;
size[u] = 1;
Tr(it,edge[u])
{
int v = it->b;
if(!del[v] && v!=fa){
Dfs(v , u);
opt[u] = max(opt[u],size[v]);
size[u] += size[v];
}
}
}
int Find(int u) // find the centre of gravity
{
Dfs(u,-1);
int who = -1 , mx = MAX_N;
for(vector<int>::iterator it = tnode.begin(); it != tnode.end(); it++)
{
opt[*it] = max(opt[*it],size[u]-size[*it]);
if(mx > opt[*it]) {
mx = opt[*it];
who = *it;
}
}
return who;
}
vector<int> all , ch[MAX_N];
void Get_dis(int u,int fa,int len,vector<int> &ch)
{
ch.push_back(len);
all.push_back(len);
Tr(it,edge[u])
{
if(it->b!=fa && !del[it->b]) {
Get_dis(it->b,u,len+it->w,ch);
}
}
}
long long calc(vector<int> dist)
{
long long ans = 0;
int pt = 0 , sz = dist.size();
sort(dist.begin(),dist.end());
for(int i = 0,j = sz - 1;i <= j;i++)
{
while(i <= j && dist[i] + dist[j] > K) {
j--;
}
if(i < j) ans += j - i;
}
return ans;
}
void Solve(int u)
{
tnode.clear();
u = Find(u); // the gravity center
all.clear(); // all of the distances
int nch = 0; // count of sons
all.push_back(0);
Tr(it,edge[u])
{
ch[nch].clear();
if(!del[it->b]) Get_dis(it->b,u,it->w,ch[nch++]);
}
Ans += calc(all);
for(int i = 0; i < nch; i++) Ans -= calc(ch[i]);
del[u] = true;
Tr(it,edge[u])
if(!del[it->b]) Solve(it->b);
}
int main()
{
int a,b,w;
while(scanf("%d%d",&N,&K),N||K)
{
for(int i = 1; i <= N; i++) edge[i].clear(),del[i]=false;
for(int i = 1; i < N; i++)
{
scanf("%d%d%d",&a,&b,&w);
edge[a].push_back(Edge(b,w));
edge[b].push_back(Edge(a,w));
}
Ans = 0;
Solve(1);
printf("%I64d\n",Ans);
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100010;
struct Edge{
int b , w;
Edge() {}
Edge(int b,int w): b(b),w(w){
}
};
#define Tr(it,x) for(vector<Edge>::iterator it = x.begin(); it!=x.end();it++)
vector<Edge> edge[MAX_N];
int N , K;
int size[MAX_N] ;
int opt[MAX_N];
bool del[MAX_N] ;
long long Ans ;
vector<int> tnode;
void Dfs(int u,int fa)
{
tnode.push_back(u);
opt[u] = 0;
size[u] = 1;
Tr(it,edge[u])
{
int v = it->b;
if(!del[v] && v!=fa){
Dfs(v , u);
opt[u] = max(opt[u],size[v]);
size[u] += size[v];
}
}
}
int Find(int u) // find the centre of gravity
{
Dfs(u,-1);
int who = -1 , mx = MAX_N;
for(vector<int>::iterator it = tnode.begin(); it != tnode.end(); it++)
{
opt[*it] = max(opt[*it],size[u]-size[*it]);
if(mx > opt[*it]) {
mx = opt[*it];
who = *it;
}
}
return who;
}
vector<int> all , ch[MAX_N];
void Get_dis(int u,int fa,int len,vector<int> &ch)
{
ch.push_back(len);
all.push_back(len);
Tr(it,edge[u])
{
if(it->b!=fa && !del[it->b]) {
Get_dis(it->b,u,len+it->w,ch);
}
}
}
long long calc(vector<int> dist)
{
long long ans = 0;
int pt = 0 , sz = dist.size();
sort(dist.begin(),dist.end());
for(int i = 0,j = sz - 1;i <= j;i++)
{
while(i <= j && dist[i] + dist[j] > K) {
j--;
}
if(i < j) ans += j - i;
}
return ans;
}
void Solve(int u)
{
tnode.clear();
u = Find(u); // the gravity center
all.clear(); // all of the distances
int nch = 0; // count of sons
all.push_back(0);
Tr(it,edge[u])
{
ch[nch].clear();
if(!del[it->b]) Get_dis(it->b,u,it->w,ch[nch++]);
}
Ans += calc(all);
for(int i = 0; i < nch; i++) Ans -= calc(ch[i]);
del[u] = true;
Tr(it,edge[u])
if(!del[it->b]) Solve(it->b);
}
int main()
{
int a,b,w;
while(scanf("%d%d",&N,&K),N||K)
{
for(int i = 1; i <= N; i++) edge[i].clear(),del[i]=false;
for(int i = 1; i < N; i++)
{
scanf("%d%d%d",&a,&b,&w);
edge[a].push_back(Edge(b,w));
edge[b].push_back(Edge(a,w));
}
Ans = 0;
Solve(1);
printf("%I64d\n",Ans);
}
return 0;
}
CROC round2 E
[cpp]
// http://poj.org/problem?id=1741
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100010;
struct Edge{
int b , w;
Edge() {}
Edge(int b,int w): b(b),w(w){
}
};
#define Tr(it,x) for(vector<Edge>::iterator it = x.begin(); it!=x.end();it++)
vector<Edge> edge[MAX_N];
int N , K;
int size[MAX_N] ;
int opt[MAX_N];
bool del[MAX_N] ;
long long Ans ;
vector<int> tnode;
void Dfs(int u,int fa)
{
tnode.push_back(u);
opt[u] = 0;
size[u] = 1;
Tr(it,edge[u])
{
int v = it->b;
if(!del[v] && v!=fa){
Dfs(v , u);
opt[u] = max(opt[u],size[v]);
size[u] += size[v];
}
}
}
int Find(int u) // find the centre of gravity
{
Dfs(u,-1);
int who = -1 , mx = MAX_N;
for(vector<int>::iterator it = tnode.begin(); it != tnode.end(); it++)
{
opt[*it] = max(opt[*it],size[u]-size[*it]);
if(mx > opt[*it]) {
mx = opt[*it];
who = *it;
}
}
return who;
}
vector<pair<int,int> > all , ch[MAX_N];
void Get_dis(int u,int fa,int len,vector<pair<int,int> > &ch,int sum)
{
ch.push_back(make_pair(sum,len));
all.push_back(make_pair(sum,len));
Tr(it,edge[u])
{
if(it->b!=fa && !del[it->b]) {
Get_dis(it->b,u,len+it->w,ch,sum+1);
}
}
}
struct BIT{
int c[MAX_N];
int maxn ;
void init(int n) {
maxn = n;
memset(c,0,sizeof(int)*n);
}
void insert(int x,int d) {
for(x++;x<=maxn;x+=x&-x) c[x] += d;
}
int sum(int x) {
int ans = 0;
for(x++;x;x-=x&-x) ans += c[x];
return ans;
}
}bit;
int L , W;
int cmp(pair<int,int> a, pair<int,int> b) {
if(a.second != b.second)return a.second < b.second;
return a.first < b.first;
}
long long calc(vector<pair<int,int> > d,bool f) //這個函數寫挫了，囧
{
long long ans = 0;
int pt = 0 , sz = d.size();
int mxd = 0;
for(int i = 0; i < sz ; i++) {
mxd = max(mxd,d[i].first);
}
bit.init(mxd+2);
sort(d.begin(),d.end(),cmp);
int cnt = 0;
int j = 0;
for(int i = sz - 1 ; i >= 0; i--) {// cnt : 單個點到根滿足條件的個數，單獨統計出來
if(f && d[i].first <= L && d[i].second <= W) cnt++;
while(j < sz && d[j].second + d[i].second <= W) {
bit.insert(d[j].first,1);
j++;
}
if(L >= d[i].first){
ans += bit.sum(min(mxd,L-d[i].first));
if(j > i) if(d[i].first+d[i].first <= L) ans --; // 自己 與 自己不能算點對，要去掉
}
}
ans += cnt * 2;
return ans;
}
void Solve(int u)
{
tnode.clear();
u = Find(u); // the gravity center
all.clear(); // all of the distances
int nch = 0; // count of sons
Tr(it,edge[u])
{
ch[nch].clear();
if(!del[it->b]) Get_dis(it->b,u,it->w,ch[nch++],1);
}
Ans += calc(all,true);
for(int i = 0; i < nch; i++) Ans -= calc(ch[i],false);
del[u] = true;
Tr(it,edge[u])
if(!del[it->b]) Solve(it->b);
}
int main()
{
int a,b,w;
while(scanf("%d%d%d",&N,&L,&W)!=EOF)
{
for(int i = 1; i <= N; i++) edge[i].clear(),del[i]=false;
for(int i = 2; i <= N; i++)
{
scanf("%d%d",&a,&w);
edge[i].push_back(Edge(a,w));
edge[a].push_back(Edge(i,w));
}
Ans = 0;
Solve(1);
printf("%I64d\n",Ans/2);
}
return 0;
}
// http://poj.org/problem?id=1741
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100010;
struct Edge{
int b , w;
Edge() {}
Edge(int b,int w): b(b),w(w){
}
};
#define Tr(it,x) for(vector<Edge>::iterator it = x.begin(); it!=x.end();it++)
vector<Edge> edge[MAX_N];
int N , K;
int size[MAX_N] ;
int opt[MAX_N];
bool del[MAX_N] ;
long long Ans ;
vector<int> tnode;
void Dfs(int u,int fa)
{
tnode.push_back(u);
opt[u] = 0;
size[u] = 1;
Tr(it,edge[u])
{
int v = it->b;
if(!del[v] && v!=fa){
Dfs(v , u);
opt[u] = max(opt[u],size[v]);
size[u] += size[v];
}
}
}
int Find(int u) // find the centre of gravity
{
Dfs(u,-1);
int who = -1 , mx = MAX_N;
for(vector<int>::iterator it = tnode.begin(); it != tnode.end(); it++)
{
opt[*it] = max(opt[*it],size[u]-size[*it]);
if(mx > opt[*it]) {
mx = opt[*it];
who = *it;
}
}
return who;
}
vector<pair<int,int> > all , ch[MAX_N];
void Get_dis(int u,int fa,int len,vector<pair<int,int> > &ch,int sum)
{
ch.push_back(make_pair(sum,len));
all.push_back(make_pair(sum,len));
Tr(it,edge[u])
{
if(it->b!=fa && !del[it->b]) {
Get_dis(it->b,u,len+it->w,ch,sum+1);
}
}
}
struct BIT{
int c[MAX_N];
int maxn ;
void init(int n) {
maxn = n;
memset(c,0,sizeof(int)*n);
}
void insert(int x,int d) {
for(x++;x<=maxn;x+=x&-x) c[x] += d;
}
int sum(int x) {
int ans = 0;
for(x++;x;x-=x&-x) ans += c[x];
return ans;
}
}bit;
int L , W;
int cmp(pair<int,int> a, pair<int,int> b) {
if(a.second != b.second)return a.second < b.second;
return a.first < b.first;
}
long long calc(vector<pair<int,int> > d,bool f) //這個函數寫挫了，囧
{
long long ans = 0;
int pt = 0 , sz = d.size();
int mxd = 0;
for(int i = 0; i < sz ; i++) {
mxd = max(mxd,d[i].first);
}
bit.init(mxd+2);
sort(d.begin(),d.end(),cmp);
int cnt = 0;
int j = 0;
for(int i = sz - 1 ; i >= 0; i--) {// cnt : 單個點到根滿足條件的個數，單獨統計出來
if(f && d[i].first <= L && d[i].second <= W) cnt++;
while(j < sz && d[j].second + d[i].second <= W) {
bit.insert(d[j].first,1);
j++;
}
if(L >= d[i].first){
ans += bit.sum(min(mxd,L-d[i].first));
if(j > i) if(d[i].first+d[i].first <= L) ans --; // 自己 與 自己不能算點對，要去掉
}
}
ans += cnt * 2;
return ans;
}
void Solve(int u)
{
tnode.clear();
u = Find(u); // the gravity center
all.clear(); // all of the distances
int nch = 0; // count of sons
Tr(it,edge[u])
{
ch[nch].clear();
if(!del[it->b]) Get_dis(it->b,u,it->w,ch[nch++],1);
}
Ans += calc(all,true);
for(int i = 0; i < nch; i++) Ans -= calc(ch[i],false);
del[u] = true;
Tr(it,edge[u])
if(!del[it->b]) Solve(it->b);
}
int main()
{
int a,b,w;
while(scanf("%d%d%d",&N,&L,&W)!=EOF)
{
for(int i = 1; i <= N; i++) edge[i].clear(),del[i]=false;
for(int i = 2; i <= N; i++)
{
scanf("%d%d",&a,&w);
edge[i].push_back(Edge(a,w));
edge[a].push_back(Edge(i,w));
}
Ans = 0;
Solve(1);
printf("%I64d\n",Ans/2);
}
return 0;
}
