这题和poj 1741是一模一样的
但是1741能AC的代码，在这里却是TLE，暂时没看出哪里出现了问题。。
AC代码：
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 40000+5 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m,k; int ans,root,tot,ptr = 1,K,son[MAXN],head[MAXN],f[MAXN],dist[MAXN],d[MAXN],sum,vis[MAXN]; struct node{int y,next,v;}tree[MAXN<<2]; void add(int u,int v,int w) {tree[ptr].y=v;tree[ptr].v=w;tree[ptr].next=head[u];head[u]=ptr++;} void getroot(int x,int fa) { son[x] = 1; f[x] = 0; for(int i=head[x];i!=-1;i=tree[i].next) { int y = tree[i].y; if(y == fa || vis[y]) continue; getroot(y,x); son[x] += son[y]; f[x] = max(f[x] , son[y]); } f[x] = max(f[x] , sum - son[x]); if(f[x] < f[root]) root = x; } void getdis(int x,int fa) { if(d[x] <= K) dist[tot++]=d[x]; for(int i=head[x];i!=-1;i=tree[i].next) { int y = tree[i].y; if(y == fa || vis[y]) continue; d[y] = d[x] + tree[i].v; getdis(y,x); } } int cal(int x,int now) { d[x]=now; tot = 0; getdis(x,0); sort(dist,dist+tot); int all = 0,left=0,right = tot-1; while(left<right) { if(dist[left]+dist[right] <= K) {all+=right-left;left++;} else right--; } return all; } void solve(int x) { ans+=cal(x,0); vis[x] = 1; for(int i=head[x];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; ans-=cal(y,tree[i].v); sum = son[y]; root = 0; getroot(y,root); solve(root); } } void init() { mem(head,-1); ptr = 1; ans = root = 0; mem(vis,0); sum=n; f[0]=INF; } int main() { while(~sf("%d%d",&n,&m)) { init(); for(int i=1;i<n;i++) { int x,y,z;char ch[2]; sf("%d%d%d%s",&x,&y,&z,ch); add(x,y,z); add(y,x,z); } sf("%d",&K); getroot(1,0); solve(root); pf("%d\n",ans); } }
1741可AC，这题TLE
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 40000+5 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m,k; int ptr = 1,head[MAXN],vis[MAXN],f[MAXN],d[MAXN]; int ans,tot,rt,sum,son[MAXN],dis[MAXN],mu[MAXN]; struct node { int y,val,next; }tree[MAXN<<2]; void init() { mem(tree,0); mem(head,-1); mem(vis,0); mem(dis,0); ans = 0; ptr = 1; sum = n; f[0] = INF; } void add(int fa,int son,int val) { tree[ptr].y = son; tree[ptr].val = val; tree[ptr].next = head[fa]; head[fa] = ptr++; } void getroot(int root,int fa) { son[root] = 1; f[root] = 0; for(int i=head[root];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y] || y == fa) continue; getroot(y,root); son[root] += son[y]; f[root] = max(son[y],f[root]); } f[root] = max(f[root],sum-son[root]); if(f[root]<f[rt]) rt = root; } void getdis(int root,int fa) { if(d[root]<=k) dis[tot++] = d[root]; for(int i=head[root];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y] || y == fa) continue; d[y] = d[root] + tree[i].val; getdis(y,root); } } int getcnt(int root,int now) { d[root] = now; tot = 0; getdis(root,0); sort(dis,dis+tot); int left =0,right = tot-1,ans=0; while(left<right) { if(dis[left]+dis[right]<=k) { ans+= right-left; left++; } else right--; } return ans; } void solve(int root) { //pf("rt%d\n",rt); ans+=getcnt(root,0); vis[root] = 1; for(int i=head[root];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; ans-=getcnt(y,tree[i].val); sum = son[y]; rt = 0; getroot(y,rt); solve(rt); } } int main() { int i,j,t,kase=1; while(~sf("%d%d",&n,&m),n+m) { init(); int x,y,z; char ch[2]; for(i=1;i<n;i++) { sf("%d%d%d%s",&x,&y,&z,ch); add(x,y,z); add(y,x,z); } sf("%d",&k); getroot(1,0); solve(rt); pf("%d\n",ans); } return 0; }
以及：http://blog.csdn.net/woshi250hua/article/details/7723400
我看起来是一样的，就是不知道TLE的原因。。