1.聪聪可可
点分治板子
然而想那个 t1[1]*t1[2]*2+t1[0]*t1[0]想了好久
就是最基本的组合方法 毕竟(2,5)和(5,2)可是要算两次的
画画图就好了(不要像我一样盯着大佬们的显然可得懵逼23333)
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #define maxn 40000 using namespace std; struct eg { int to,v,nxt; }b[maxn]; ,f[maxn],sz[maxn],vis[maxn],d[maxn]={},ans,root,sum,t1[]; int gcd(int x,int y){return y?gcd(y,x%y):x;} void link(int x,int y,int z) { b[++tot].nxt=head[x]; b[tot].to=y; b[tot].v=z; head[x]=tot; } void getroot(int u,int fa) { sz[u]=,f[u]=; for (int i=head[u];i;i=b[i].nxt) { int t=b[i].to; if (vis[t]||t==fa) continue; getroot(t,u); sz[u]+=sz[t]; f[u]=max(f[u],sz[t]); } f[u]=max(f[u],sum-sz[u]); if (f[root]>f[u]) root=u; } void getdeep(int x,int fa) { t1[d[x]]++; for (int i=head[x];i;i=b[i].nxt) { int t=b[i].to; if (vis[t]||t==fa) continue; d[t]=(d[x]+b[i].v)%; getdeep(t,x); } } int cal(int x,int vv) { d[x]=vv%; t1[]=t1[]=t1[]=; getdeep(x,); ]*t1[]*+t1[]*t1[]; } void work(int x) { ans+=cal(x,); vis[x]=; for (int i=head[x];i;i=b[i].nxt) { int t=b[i].to; if (vis[t]) continue; ans-=cal(t,b[i].v); sum=sz[t]; root=; getroot(t,); work(root); } } int main() { int n; scanf ("%d",&n); ;i<n;++i) { int x,y,w; scanf ("%d%d%d",&x,&y,&w); link(x,y,w); link(y,x,w); } root=;f[]=n,sum=n; getroot(,); work(root); int l=gcd(ans,n*n); cout<<(ans/l)<<"/"<<(n*n/l); ; }
2.POJ1741 树上的点对
考试的时候碰到这题 感觉就像bilegou
然后我这个天大的sb就发挥我的本性打了个链剖哈哈哈哈哈哈哈哈 还没打完
考完之后老师说正解是点分治 然而考前我们是没有学过这玩意儿的(和善
去学了一下 只感觉dalao的论文写的真好
#include<iostream> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cstring> #define maxn 20010 using namespace std; ,dep[maxn],sz[maxn],f[maxn],vis[maxn],d[maxn]; int sum,root,n,k,ans; void link(int x,int y,int z) { nxt[++tot]=head[x]; to[tot]=y; dis[tot]=z; head[x]=tot; } void gr(int x,int fa) { sz[x]=;f[x]=; for (int i=head[x];i;i=nxt[i]) { int t=to[i]; if (t==fa||vis[t]) continue; gr(t,x); sz[x]+=sz[t]; f[x]=max(f[x],sz[t]); } f[x]=max(f[x],sum-sz[x]); if (f[root]>f[x]) root=x; } void gd(int x,int fa) { dep[++dep[]]=d[x]; for (int i=head[x];i;i=nxt[i]) { int t=to[i]; if (t==fa||vis[t]) continue; d[t]=d[x]+dis[i]; gd(t,x); } } int work(int x,int v) { d[x]=v;dep[]=; gd(x,); sort(dep+,dep+dep[]+); ; ,r=dep[];l<r;) { if (dep[l]+dep[r]<=k) ans+=r-l,l++; else r--; } return ans; } void dfs(int u) { ans+=work(u,); vis[u]=; for (int i=head[u];i;i=nxt[i]) { int t=to[i]; if (vis[t]) continue; ans-=work(t,dis[i]); sum=sz[t]; root=; gr(t,); dfs(root); } } int main() { //freopen ("in.txt","r",stdin); //freopen ("out.txt","w",stdout); while (scanf ("%d%d",&n,&k)) { memset(vis,,sizeof(vis)); memset(head,,sizeof(head)); root=,ans=,tot=; ) break; ;i<n;++i) { int x,y,z; scanf ("%d%d%d",&x,&y,&z); link(x,y,z); link(y,x,z); } sum=n,f[]=0x7fffffff; gr(,); dfs(root); cout<<ans<<endl; } ; }