题目链接: Tree https://vjudge.net/problem/POJ-1741
树分治参考资料: 09 年漆子超 https://wenku.baidu.com/view/e087065f804d2b160b4ec0b5.html ZigZagK 的博客 https://blog.csdn.net/zzkksunboy/article/details/70244945 [点分治] 的学习笔记和众多例题 https://blog.csdn.net/nixinyis/article/details/65445466
以上的资料是我看过好的, 具体算法分析实现都讲明白, 贴一下我的代码 (由于 poj 交不了题还没 a)
- #include<bits/stdc++.h>
- #include<set>
- #include<cstdio>
- #include<iomanip>
- #include<iostream>
- #include<string>
- #include<cstring>
- #include<algorithm>
- #define pb push_back
- #define ll long long
- #define fi first
- #define se second
- #define PI 3.14159265
- #define ls l,m,rt<<1
- #define rs m+1,r,rt<<1|1
- #define eps 1e-7
- #define pii pair<int,int>
- typedef unsigned long long ull;
- const int mod=1e3+5;
- const ll inf=0x3f3f3f3f3f3f3f;
- const int maxn=1e5+5;
- using namespace std;
- int n,m,head[maxn],to[maxn*2],w[maxn*2],nxt[maxn*2],cnt,k,siz[maxn],dep[maxn],rt,mx[maxn],s;
- int now[maxn];
- bool vis[maxn];
- ll ans;
- void add_edge(int x,int y,int l)
- {
- to[++cnt]=y;w[cnt]=l;nxt[cnt]=head[x];head[x]=cnt;
- }
- void dfs_rt(int v,int f)// 找重心
- {
- siz[v]=1;mx[v]=0;
- //cout<<v<<"SSS"<<f<<endl;
- for(int i=head[v];i;i=nxt[i])
- {
- if(to[i]==f||vis[to[i]])continue;
- dfs_rt(to[i],v);
- siz[v]+=siz[to[i]];
- mx[v]=max(siz[to[i]],mx[v]);
- }
- mx[v]=max(s-siz[v],mx[v]);
- if(rt==-1||mx[v]<mx[rt])rt=v;
- }
- void get_dep(int v,int f)
- {
- now[++now[0]]=dep[v];
- for(int i=head[v];i;i=nxt[i])
- {
- if(vis[to[i]]||to[i]==f)continue;
- dep[to[i]]=dep[v]+w[i];
- get_dep(to[i],v);
- }
- }
- int get_sum(int v,int dis)
- {
- int cn=0;now[0]=0;
- dep[v]=dis;get_dep(v,-1);
- sort(now+1,now+1+now[0]);
- int l=1,r=now[0];
- while(l<r)if(now[l]+now[r]<=k)cn+=r-l,l++;else r--;
- return cn;
- }
- void get_ans(int v)
- {
- vis[v]=true;ans+=get_sum(v,0);
- cout<<"###"<<ans<<endl;
- for(int i=head[v];i;i=nxt[i])
- {
- if(vis[to[i]])continue;
- ans-=get_sum(to[i],w[i]);
- cout<<"SSS"<<ans<<endl;
- rt=-1;s=siz[to[i]];dfs_rt(to[i],v);
- get_ans(rt);
- }
- }
- int main()
- {
- while(~scanf("%d %d",&n,&k))
- {
- if(!n&&!k)break;
- memset(head,0,sizeof(head));cnt=0;
- memset(vis,0,sizeof(vis));
- for(int i=0;i<n-1;i++)
- {
- int u,v,l;
- scanf("%d %d %d",&u,&v,&l);
- add_edge(u,v,l);add_edge(v,u,l);
- }
- rt=-1;s=n;dfs_rt(1,-1);
- get_ans(rt);
- printf("%lld\n",ans);
- }
- return 0;
- }
第二个例题: 2152: 聪聪可可 https://www.lydsy.com/JudgeOnline/problem.php?id=2152
题解跟上面那题差不多, 计算出的到根的距离 %3 之后的值的个数, now[0],now[1],now[2]. 答案就是 now[0]*now[0]+2*now[1]*now[2]
- #include<bits/stdc++.h>
- #include<set>
- #include<cstdio>
- #include<iomanip>
- #include<iostream>
- #include<string>
- #include<cstring>
- #include<algorithm>
- #define pb push_back
- #define ll long long
- #define fi first
- #define se second
- #define PI 3.14159265
- #define ls l,m,rt<<1
- #define rs m+1,r,rt<<1|1
- #define eps 1e-7
- #define pii pair<int,int>
- typedef unsigned long long ull;
- const int mod=1e3+5;
- const ll inf=0x3f3f3f3f3f3f3f;
- const int maxn=2e4+5;
- using namespace std;
- int n,m,head[maxn],to[maxn*2],w[maxn*2],nxt[maxn*2],cnt,k,siz[maxn],dep[maxn],rt,mx[maxn],s;
- int now[maxn];
- bool vis[maxn];
- int ans;
- void add_edge(int x,int y,int l)
- {
- to[++cnt]=y;w[cnt]=l;nxt[cnt]=head[x];head[x]=cnt;
- }
- void dfs_rt(int v,int f)// 找重心
- {
- siz[v]=1;mx[v]=0;
- for(int i=head[v];i;i=nxt[i])
- {
- if(to[i]==f||vis[to[i]])continue;
- dfs_rt(to[i],v);
- siz[v]+=siz[to[i]];
- mx[v]=max(siz[to[i]],mx[v]);
- }
- mx[v]=max(s-siz[v],mx[v]);
- if(rt==-1||mx[v]<mx[rt])rt=v;
- }
- void get_dep(int v,int f)
- {
- now[(dep[v])%3]++;
- for(int i=head[v];i;i=nxt[i])
- {
- if(vis[to[i]]||to[i]==f)continue;
- dep[to[i]]=dep[v]+w[i];
- get_dep(to[i],v);
- }
- }
- int get_sum(int v,int dis)
- {
- int cn=0;now[0]=0,now[1]=0,now[2]=0;
- dep[v]=dis;get_dep(v,-1);
- cn+=now[0]*now[0]+2*now[1]*now[2];
- return cn;
- }
- void get_ans(int v)
- {
- vis[v]=true;ans+=get_sum(v,0);
- for(int i=head[v];i;i=nxt[i])
- {
- if(vis[to[i]])continue;
- ans-=get_sum(to[i],w[i]);
- rt=-1;s=siz[to[i]];dfs_rt(to[i],v);
- get_ans(rt);
- }
- }
- int main()
- {
- while(~scanf("%d",&n))
- {
- memset(head,0,sizeof(head));cnt=0;
- memset(vis,0,sizeof(vis));
- for(int i=0;i<n-1;i++)
- {
- int u,v,l;
- scanf("%d %d %d",&u,&v,&l);
- add_edge(u,v,l);add_edge(v,u,l);
- }
- rt=-1;s=n;dfs_rt(1,-1);
- get_ans(rt);
- int sum=n*n;
- int tmp=__gcd(sum,ans);
- ans/=tmp;sum/=tmp;
- printf("%d/%d\n",ans,sum);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2693713.html