bzoj 1316:ツリー上の問い合わせ(ポイント分治)

1829 ワード
分治を施す
1316:ツリー上の問い合わせ
Time Limit: 10 Sec  
Memory Limit: 162 MB
Submit: 564  
Solved: 150
[ Submit][ Status][ Discuss]
Description
1本のn個の点の重み付きルートツリー、p個の問い合わせがあり、毎回ツリーに長さLenの経路があるかどうかを尋ねるが、もしそうであれば、出力Yes No.
Input
第1行の2つの整数n、pはそれぞれ点の個数と質問の個数を表す.次のn-1行の各行の3つの数x、y、cは、1本の木の辺x→yがあることを示し、長さはc.次のp行の各行の1つの数Lenは、質問ツリーの中に1本の長さLenの経路があるかどうかを示す.
Output
出力はp行、YesまたはNo.
Sample Input
6 4 1 2 5 1 3 7 1 4 1 3 5 2 3 6 3 1 8 13 14
Sample Output
Yes Yes No Yes
HINT
30%のデータ、n≦100.100%のデータ、n≦10000、p≦100、長さ≦100000.この問題を完成したらPOJ 3237 Treeを見ることができます
Source
[ Submit][ Status][ Discuss]
問題解:ポイント管理
#include  
#include  
#include  
#include  
#include  
#define N 30003  
using namespace std;  
int n,m,tot,num[10000003];  
int point[N],next[N],v[N],len[N],cnt,root,sum,vis[N];  
int f[N],deep[N],mp[N],d[N],ak[N],mark[N],son[N],g[N];  
void add(int x,int y,int z)  
{  
    tot++; next[tot]=point[x]; point[x]=tot; v[tot]=y; len[tot]=z;  
    tot++; next[tot]=point[y]; point[y]=tot; v[tot]=x; len[tot]=z;  
    //cout<1&&g[j]*2==ak[i])  
         mark[i]+=opt*num[j]*(num[j]-1);   
       while (l0||!ak[i]) printf("Yes
");  
     else printf("No
");  
}
qemu-kvmで作ったimgイメージをマウントする
hdu 2802母関数はそれぞれ制限のある経典が深い.