題目給出一棵樹(N<=10000)以及所有邊的權(quán)(<=10000). 現(xiàn)在要求對任意查詢Q(<=10^8), 判斷是否存在一條邊權(quán)之和恰好為Q的路徑.
標(biāo)程的方法暫時沒看懂= =... 
我用樹的分治做(更多相關(guān)內(nèi)容見09國家集訓(xùn)隊漆子超的論文)
考慮一棵以root為根的子樹, 那么在這棵子樹中, 有多少條 v1->root->v2 的路徑長恰好為Q呢? 可以先DFS一次子樹, 求出所有點到root的距離, 將這些距離排個序,  就能在klogk的時間里求出滿足和為Q的組合數(shù)count[root,Q]. 但是這樣把路徑重疊, 也就是v1->v'->root->v'->v2的情況也算進(jìn)去了.  考慮不合法的狀態(tài), 如果有邊重復(fù), 那么其中肯定包含root到某個兒子的邊, 也就是形如v1->chi->root->chi->v2. 所以count[root,Q]中不合法路徑數(shù)為sigma(count[chi,Q-2*dist[root][chi]]), 求出來減去即可.
這樣處理完以root為根的樹后, 結(jié)點root已經(jīng)沒有用了. 也就是說剩下的只須處理它的所有兒子樹,  轉(zhuǎn)化為新的獨立問題.
這樣不斷地處理樹, 將樹分成新子樹, 最后完成所有子樹的統(tǒng)計.

恰當(dāng)選擇每次拆分的樹根可以使復(fù)雜度變成nlogn, 否則總復(fù)雜度仍然是n^2. 一個較方便的規(guī)則是: 選擇樹的平衡點, 也就是拿掉這個點后形成的森林里, max(|tree[i]|)最小.
這樣的點可以對樹DFS一次做DP求得. pku1655就是解決這個問題.

ps.pku1741與此題幾乎完全一樣, 唯一不同的是那題是求dist<=Q的路徑的數(shù)量.

代碼:

  1#include <iostream>
  2#include <algorithm>
  3using namespace std;
  4
  5//#define DEBUG
  6
  7const int MAX_V = 11000;
  8const int MAX_E = MAX_V*5;
  9
 10struct EDGE{
 11  int v,e,w;
 12}edg[MAX_E];
 13int se, gg[MAX_V];
 14bool ok[MAX_E];
 15int vis[MAX_V], stamp;
 16int que[MAX_V*5], sque, pque;
 17int card[MAX_V], chm[MAX_V], sum[MAX_V], det[MAX_V];
 18int gdd[MAX_V],sdd;
 19int ans;
 20int N,L; 
 21
 22void addedge(int u, int v, int w)
 23{
 24  edg[se].v=v; edg[se].w=w; edg[se].e=gg[u]; gg[u]=se++;
 25  edg[se].v=u; edg[se].w=w; edg[se].e=gg[v]; gg[v]=se++;
 26}
 27
 28void dfsplus(int rt, int ss, int di, int &idx, int &cnt) 
 29{
 30  //求距離的同時找重心
 31  vis[rt]=stamp;
 32  chm[rt]=0, card[rt]=1;
 33  gdd[sdd++]=di;
 34  for(int j=gg[rt]; j>0; j=edg[j].e){
 35    if(ok[j])continue;
 36    int v=edg[j].v;
 37    if(vis[v]==stamp)continue;
 38    dfsplus(v, ss, di+edg[j].w, idx, cnt);
 39    card[rt]+=card[v];
 40    chm[rt]=max(chm[rt],card[v]);
 41  }
 42  chm[rt]=max(chm[rt],ss-card[rt]);
 43  if(chm[rt]<cnt)
 44    idx=rt, cnt=chm[rt];
 45}
 46
 47int matchdist(int d)
 48{
 49  int ret=0;
 50  sort(gdd,gdd+sdd);
 51  int q1=0, q2=sdd-1;
 52  //線性的掃描求組合數(shù), 可惜前面的排序多了個logn
 53  while(q1<=q2){
 54    if(gdd[q1]+gdd[q2]<d)q1++;
 55    else if(gdd[q1]+gdd[q2]>d)q2--;
 56    else{
 57      if(gdd[q1]==gdd[q2]){
 58        ret+=(q2-q1)*(q2-q1+1)/2; 
 59        break;
 60      }
 61      else{
 62        int p1=q1+1, p2=q2-1;
 63        while(p1<sdd && gdd[p1]==gdd[q1]) p1++;
 64        while(p2>=0 && gdd[p2]==gdd[q2]) p2--;
 65        ret+=(p1-q1)*(q2-p2);
 66        q1=p1, q2=p2;
 67      }
 68    }
 69  }
 70  return ret;
 71}
 72
 73void solve()
 74{
 75  int i,j,k;  
 76  pque=sque=0;
 77  ans=0;
 78  stamp=0;
 79  memset(vis,0,sizeof(vis));
 80  det[1]=-1; sum[1]=N;
 81  que[sque++]=1;
 82  while(pque!=sque){
 83    int u=que[pque++];
 84    int idx=u, cnt=N+1;
 85    sdd=0;
 86    ++stamp;
 87    dfsplus(u, sum[u], 0, idx, cnt);
 88    if(det[u]>0 && L-det[u]*2>=0){
 89      //減去它父親的非法路徑數(shù)
 90      ans-=matchdist(L-det[u]*2);
 91    }
 92    u=idx;
 93    sdd=0;
 94    ++stamp;
 95    dfsplus(u, sum[u], 0, idx, cnt);
 96    //加上自己的總路徑數(shù)
 97    ans+=matchdist(L);
 98    for(j=gg[u]; j>0; j=edg[j].e){
 99      if(ok[j])continue;
100      int v=edg[j].v;
101      det[v]=edg[j].w;
102      ok[j^1]=true; //切斷子樹和父親的邊
103      sum[v]=card[v];
104      que[sque++]=v;
105    }
106  }
107  if(ans>0) puts("AYE");
108  else puts("NAY");
109}
110
111int main()
112{
113  int i,j,k,u,v,w;
114  while(true){
115    scanf("%d",&N);
116    if(N==0)break;
117    se=2;
118    memset(gg,0,sizeof(gg));
119    for(u=1; u<=N; u++){
120      while(true){
121        scanf("%d",&v);
122        if(v==0)break;
123        scanf("%d",&w);
124        addedge(u,v,w);
125      }
126    }
127    while(true){
128      scanf("%d",&L);
129      if(L==0)break;
130      memset(ok,false,sizeof(ok));
131      solve();
132    }
133    printf(".\n");
134  }
135}
136