本文共 2199 字，大约阅读时间需要 7 分钟。
在BZ上连续MLE n次后,终于A了.
自己YY的动态点分写法,思路还是很清楚的,但是比较卡内存.
用到了MAP导致复杂度比其他的代码多了一个log,看来需要去借鉴一下别人怎么写的.
updata in 2017-05-25:
发现了一些没必要储存的东西.
1. 存储当前重心某子树堆的位置的MAP可以利用在重心树上的儿子记录此信息.
2.求树上距离可以用RMQ,没必要直接拿MAP记下来.
改完这两个令我颇不舒服的地方,复杂度就正常多了.
1 /* 2 动态树分治 3 BZOJ1095 4 全局路径查询 5 单点修改,全局查询 6 */ 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 #define ll long long 23 #define up(i,j,n) for(int i=j;i<=n;++i) 24 #define db double 25 #define piii pair< pair ,int> 26 #define pb push_back 27 #define FILE "dealing" 28 #define eps 1e-8 29 template inline bool cmin(T&a,T b){ return a>b?a=b,true:false;} 30 template inline bool cmax(T&a,T b){ return a inline T squ(T a){ return a*a;} 32 const int maxn=100000+10,base=23,limit=3e8,inf=2000000; 33 int read(){ 34 int x=0,f=1,ch=getchar(); 35 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 36 while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar(); 37 return x*f; 38 } 39 int n,Q; 40 vector E[maxn]; 41 struct dui{ 42 priority_queue q,q2; 43 void pop(){ 44 while(!q.empty()&&!q2.empty()&&q.top()==q2.top())q.pop(),q2.pop(); 45 if(!q.empty())q.pop(); 46 } 47 int top(){ 48 while(!q.empty()&&!q2.empty()&&q.top()==q2.top())q.pop(),q2.pop(); 49 if(!q.empty())return q.top(); 50 else return -1; 51 } 52 void erase(int x){ 53 q2.push(x); 54 while(!q.empty()&&!q2.empty()&&q.top()==q2.top())q.pop(),q2.pop(); 55 } 56 void push(int x){ 57 q.push(x); 58 while(!q.empty()&&!q2.empty()&&q.top()==q2.top())q.pop(),q2.pop(); 59 } 60 int getans(){ 61 int s1=top();pop(); 62 int s2=top();push(s1); 63 if(s1==-1)return -1; 64 if(s2==-1)return -2; 65 return s1+s2; 66 } 67 }All,DA[maxn],MA[maxn<<1];int cnt=0; 68 int siz[maxn],vis[maxn],Mx[maxn],dep[maxn]; 69 int getsize(int x,int fa){ 70 siz[x]=1; 71 for(int i=0;i
转载于:https://www.cnblogs.com/chadinblog/p/6901946.html
